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

技术分享 11个月前 (03-12) 0 999+

简介

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

深度优先遍历(DFS)

遍历所有节点

        /// <summary>         /// 邻接表实现DFS         /// </summary>         /// <param name="startIndex"></param>         public void DFSTraverse(int startIndex)         {              if (startIndex < 0 || startIndex >= _graph.Count)                 return;              //记录一下已经访问过的，避免死循环             if (_visited[startIndex])                 return;             _visited[startIndex] = true;               //前序遍历             Console.WriteLine($"index={startIndex}");              if (_graph[startIndex]?.Count > 0)             {                 foreach (var item in _graph[startIndex])                 {                     DFSTraverse(item.Indegree);                 }             }              //后序遍历             //Console.WriteLine($"index={index}");         } 		/// <summary>         /// 邻接矩阵实现DFS         /// </summary>         /// <param name="startIndex"></param>         public void DFSTraverse(int startIndex)         {             //记录一下已经访问过的，避免死循环             if (_visited[startIndex])                 return;              _visited[startIndex] = true;              //前序遍历             Console.WriteLine($"index={startIndex}");              for (int i = 0; i < _visited.Length; i++)             {                 //为0代表未使用                 if (_matrix[startIndex, i] == 0)                     continue;                  DFSTraverse(i);             }              //后序遍历             //Console.WriteLine($"index={index}");          }

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

遍历所有路径

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

以此图为例，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数组，在进入节点时标记正在访问，退出节点时撤销标记。这样就能形成一个完整的遍历路径。

        public void Traverse(int src,int dest)          {             if (src < 0 || src >= _graph.Count)                 return;              //防止形成死循环             if (_visited[src])                 return;                           _visited[src] = true;             //在前序位置加入遍历路径             _path.AddLast(src);             if (src == dest)             {                 Console.WriteLine($"find path:{string.Join("=>", _path)}");             }               foreach (var item in _graph[src])             {                 Traverse(item.Indegree, dest);             }                          _path.RemoveLast();             //在后序位置撤销标记             _visited[src] = false;         }

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

广度遍历优先(BFS)

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

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

        public void BFSTraverse(int startIndex)         {             Queue<int> queue=new Queue<int>();             queue.Enqueue(startIndex);             //标记节点已被访问，避免死循环。             _visited[startIndex]=true;              while (queue.Count > 0)             {                 var cur=queue.Dequeue();                 Console.WriteLine($"cur:{cur}");                  foreach (var e in _graph[cur])                 {                     //已经访问过了就不再访问                     if (!_visited[e.Indegree])                     {                         queue.Enqueue(e.Indegree);                         _visited[e.Indegree] = true;                     }                 }             }         }