基于范围的for循环和普通for循环深度优先搜索实现的区别

Question

我正在尝试为图形数据结构实现深度优先搜索算法，我的函数如下所示：

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);
        }
    }
}

当我像上面那样使用普通的 for 循环时，当我调用函数 dfs(0, Adjacency_List, visited) 时，访问的数组不会更新到图形的第一个顶点之外；

但是，当我将普通的 for 循环更改为基于范围的 for 循环时，如下所示：

    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
        }
    }

每当调用 dfs 函数时，访问的数组都会相应更新。我不太确定为什么第二个实现有效，但我的初始实现没有，因为这两个实现似乎具有相似的逻辑。感谢您的帮助！

编辑：v_Int 是我声明为整数向量的 typedef

Answer 1

在第一个实现中，邻居不是 i，它是 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);
}

基于范围的for循环和普通for循环深度优先搜索实现的区别

Difference between range-based for loop and normal for loop Depth-First Search implementation

c++

for-loop

range-based-loop