浅谈图的深层优先和广度优先遍历（栈实现，循环内层嵌套递归实现）（c++）

最近刚好学到了图的深层优先遍历（DFS），发现了一些误区，比如“Skiena'sAlgorithm Design Manual第169页; Jeff Edmonds'How to Think about Algorithms, 第175–178页; Gilberg and ForouzanData Structures: A Pseudocode Approach Using C, 第497页。”

金润蔚

1294人浏览 · 2022-05-12 17:47:54

金润蔚 · 2022-05-12 17:47:54 发布

最近刚好学到了图的深层优先遍历（DFS），发现了一些误区，比如“Skiena's Algorithm Design Manual 第 169页; Jeff Edmonds' How to Think about Algorithms, 第 175–178页; Gilberg and Forouzan Data Structures: A Pseudocode Approach Using C, 第 497页。”

包括维基百科中也出现了同样的错误，也就是直接将广度优先遍历（BFS）中的queue直接替换成了stack，显然会出现一些问题。

https://11011110.github.io/blog/2013/12/17/stack-based-graph-traversal.html

这个网站中指出了这些问题。

简单概括：把queue直接替换成stack会先访问一些（如果使用DFS）应该在后面访问的节点。

BFS(s)
{for( each vertex v){
    flag(v) = false}//flag用于标记已经访问过的顶点。先全部标记为false
    queue q;
    q.push(s);
    flag(s) = true;//访问过了源定点，标记为true
    while{!q.empty()){
        v = q.front();
        q.pop();
         for(顶点v连接的顶点w){
           if(flag（v） = false){//如果没有访问
            flag(v) = true;//访问过了
            q.push(v);//压入队列中}
}
}

这是一种使用queue来广度优先（BFS）的思路

也就是说：

1、访问列表里所有的顶点为false（未访问）

2、创建queue

3、将源顶点压入queue里

4、弹出queue里的一个顶点（遍历实际在这里进行）

5、把这个顶点里的所有没有访问过的邻居（有线连着的）依次压入栈里

6、重复4-5直到栈为空

例如：

BFS遍历顺序：2->8->1->4->0->9->3->7->5->6

时间复杂程度：O(顶点+边数)

接下来是广度优先遍历（DFS）

1、和BFS一样，先把访问列表全部设成false
2、DFS(v){
flag[v] = true;
for(v的每一个邻居w){
if(flag[w] = false){
DFS(w);}}

这里代码的难点在

DFS（v）

for(v的每一个邻居w){
if(flag[w] = false){
DFS(w);}

}

这是一个循环嵌套递归

在编译器中大概是这样的

1、进入函数调用时循环被“暂停”。

2、新的递归调用开始for并再次循环，在再次调用函数时暂停，依此类推。

2（pause)->8(pause)->0

8(continiue)->9(pause)->1(pause)->3(pause)->4

3->5(pause)->6(pause)->7

6(continue):所有的邻居(7、5)都访问过了（使用visited list，不满足if(flag[w] == false)里面的东西不再执行.

5（continue):3,6访问过了，if语句不再执行。

以此类推直到2

遍历结果:2 8 0 9 1 3 4 5 6 7

循环嵌套递归也可以理解为

for (  )
{
    for ( )
    {
        for (  )
        {
        }
    }
}

很多个for嵌套在一起

其实会发现DFS的操作似乎和栈（stack）有类似的地方：

使用栈来实现（仿递归函数）

1、创建stack

2、flag[源顶点] = true;

3、把当前顶点 v 压入栈里（遍历发正在这里）

4、根据顺序，把v的一个邻居压入栈中

5、如果栈顶里的顶点所有邻居都访问到了，弹出，没有访问到，继续压入，直到栈为空。

使用代码表示：

vector<int> visited(n,0);
        stack<int> s;
        visited[2] =1;
        s.push(2);
    cout << "2"<<endl;
       while(!s.empty()){
            int temp=s.top();
             int check = 0;
            for(int i = 0; i< graph[temp].size();i++){
                if(visited[graph[temp][i]] == 1){
                    check ++;
                }
            }
            if(check == graph[temp].size()){
                s.pop();
            }
           if(s.size() ==0){return;}
            int temp1 = s.top();
            for( int i = 0; i<graph[temp1].size();i++){
                if(visited[graph[temp1][i]] ==0){
                    s.push(graph[temp1][i]);
                    visited[graph[temp1][i]] =1;
                    cout << "遍历中"<<graph[temp1][i]<<endl;
                    break;
                }
            }
        }
}

代码应该还可以优化