重生之数据结构与算法----图的遍历

简介

上文讲到，图的本质是多叉树。因此主要遍历方式还是DFS与BFS。
唯一的区别在于，树结构中不存在环，而图中可能回成环。因此我们需要记录一下已经访问过的节点，避免死循环。
深度优先遍历(DFS)

遍历所有节点

1.         /// <summary>
2.         /// 邻接表实现DFS
3.         /// </summary>
4.         /// <param name="startIndex"></param>
5.         public void DFSTraverse(int startIndex)
6.         {
8.             if (startIndex < 0 || startIndex >= _graph.Count)
9.                 return;
11.             //记录一下已经访问过的，避免死循环
12.             if (_visited[startIndex])
13.                 return;
14.             _visited[startIndex] = true;
17.             //前序遍历
18.             Console.WriteLine($"index={startIndex}");
20.             if (_graph[startIndex]?.Count > 0)
21.             {
22.                 foreach (var item in _graph[startIndex])
23.                 {
24.                     DFSTraverse(item.Indegree);
25.                 }
26.             }
28.             //后序遍历
29.             //Console.WriteLine($"index={index}");
30.         }
31.                 /// <summary>
32.         /// 邻接矩阵实现DFS
33.         /// </summary>
34.         /// <param name="startIndex"></param>
35.         public void DFSTraverse(int startIndex)
36.         {
37.             //记录一下已经访问过的，避免死循环
38.             if (_visited[startIndex])
39.                 return;
41.             _visited[startIndex] = true;
43.             //前序遍历
44.             Console.WriteLine($"index={startIndex}");
46.             for (int i = 0; i < _visited.Length; i++)
47.             {
48.                 //为0代表未使用
49.                 if (_matrix[startIndex, i] == 0)
50.                     continue;
52.                 DFSTraverse(i);
53.             }
55.             //后序遍历
56.             //Console.WriteLine($"index={index}");
57.         }

复制代码

可以看到，与多叉树的深度优先并无区别，就多了一个数组。

遍历所有路径

在树结构中，遍历所有路径和遍历所有节点，是没区别的。因为根节点到叶节点的过程是单向，所以他们之间的路径是唯一的。
但在图中，因为环的存在。所以从根节点到叶节点的过程路径会有很多种。因此在图的遍历中，图的路径需要穷举。

以此图为例，0节点到4节点，就有5种路径。
find path:0=>1=>2=>3=>4
find path:0=>1=>3=>4
find path:0=>1=>4
find path:0=>3=>4
find path:0=>4

对于图来说，由起点stc到目标节点dest的路径很多，我们需要一个onPath数组，在进入节点时标记正在访问，退出节点时撤销标记。这样就能形成一个完整的遍历路径。

1.         public void Traverse(int src,int dest)
2.         {
3.             if (src < 0 || src >= _graph.Count)
4.                 return;
6.             //防止形成死循环
7.             if (_visited[src])
8.                 return;
10.             
11.             _visited[src] = true;
12.             //在前序位置加入遍历路径
13.             _path.AddLast(src);
14.             if (src == dest)
15.             {
16.                 Console.WriteLine($"find path:{string.Join("=>", _path)}");
17.             }
20.             foreach (var item in _graph[src])
21.             {
22.                 Traverse(item.Indegree, dest);
23.             }
25.            
26.             _path.RemoveLast();
27.             //在后序位置撤销标记
28.             _visited[src] = false;
29.         }

复制代码

为什么要在后序位置撤销标记？如果不撤销。就类似遍历所有节点一样。遇到了重复节点就退出了，而漏掉了其它可能的路径。因此当节点退出时撤销标记。再往右探测可能的路径。直到遍历完整个图。
广度遍历优先(BFS)

同理可得，对于图的BFS算法。也只要加入一个visited数组来避免死循环即可。

理论上BFS遍历也需要遍历完所有节点与所有路径，但一般情况下，BFS只用来寻找最短路径。因为BFS算法是以层位维度，一层一层的搜索。第一次遇到的目标节点，那必然是最短路径。

1.         public void BFSTraverse(int startIndex)
2.         {
3.             Queue<int> queue=new Queue<int>();
4.             queue.Enqueue(startIndex);
5.             //标记节点已被访问，避免死循环。
6.             _visited[startIndex]=true;
8.             while (queue.Count > 0)
9.             {
10.                 var cur=queue.Dequeue();
11.                 Console.WriteLine($"cur:{cur}");
13.                 foreach (var e in _graph[cur])
14.                 {
15.                     //已经访问过了就不再访问
16.                     if (!_visited[e.Indegree])
17.                     {
18.                         queue.Enqueue(e.Indegree);
19.                         _visited[e.Indegree] = true;
20.                     }
21.                 }
22.             }
23.         }

复制代码

剩下的两种，记录所在层与记录权重。不在赘述，可以参考多叉树的BFS三种遍历代码。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！