I’m trying to implement a depth first search algorithm for a graph data structure and my function looks like this:

void dfs(int x, vector <v_Int>& Adjacency_List, v_Int& visited) { visited[x] = 1; //Mark current vertex as visited for (int i = 0; i < Adjacency_List[x].size(); i++) { //Iterate through all neighbours of vertex x if (visited[i] != 1) { //If neighbour not visited, recursively go there dfs(i, Adjacency_List, visited); } } }

When I used a normal for loop like I did above, the visited array does not get updated beyond the first vertex of the graph when I call the function dfs(0, Adjacency_List, visited);

However, when I change the normal for loop to a range based for loop like so:

for (auto &v : Adjacency_List[x]) { //Iterate through all neighbours of vertex x if (!visited[v]) { dfs(v, Adjacency_List, visited); //If neighbour not visited, recursively go there } }

The visited array gets updated accordingly whenever the dfs function is called. I’m not too sure why the 2nd implementation works but my initial implementation doesn’t since both implementations seem to have similar logics. Thank you for your help!

Edit: v_Int is a typedef I declared to be a vector of integers

## Answer

In first implementation, neighbour is not i, its Adjacency_List[x][i].

int neighbour = Adjacency_List[x][i]; if (visited[neighbour] != 1) { //If neighbour not visited, recursively go there dfs(neighbour, Adjacency_List, visited); }