直观理解：图遍历算法DFS和BFS

大家好，欢迎来到IT知识分享网。

深度优先遍历（Depth First Search，简称 DFS） 与广度优先遍历（Breath First Search，简称BFS）是图论中两种非常重要的遍历算法，生产上广泛用于拓扑排序，寻路，搜索引擎，爬虫等。下面我们通过一个图，直观的展示两种遍历算法的过程。

深度优先遍历

深度优先遍历（DFS）简单来说就是每一次遍历到一个顶点的时候，如果这个顶点已经遍历过，那么就return，返回到上一层（也就是所谓的回溯）；如果该顶点符合遍历条件，就将当前顶点加入已遍历集合中，然后随机选择该顶点的一个邻接顶点，重复上述遍历过程。回溯到起点，没有任何其他顶点可以遍历为止。深度优先遍历需要对遍历过的顶点进行标记，否则会在递归的时候陷入死循环。深度优先遍历的过程如图2所示。

深度优先遍历的伪代码结构描述如下：

// 图的深度优先遍历 void dfs( int v ){ visited[v] = true; //顶点遍历状态 for( int i: G.adj(v) ){ if( !visited[i] ) dfs(i); } }

广度优先遍历
  广度优先遍历（BFS）简单来说就是每次选择一个顶点进行遍历，遍历时需要将当前顶点的未遍历邻接顶点加入到一个队列中，然后依次对当前顶点的邻接顶点重复上述遍历过程，直到队列中没有任何需要遍历的顶点为止。在广度优先遍历时，会从起点开始“一层一层”扩展的方法来遍历，扩展时每发现一个未遍历过的顶点时，就将这个顶点加入到队列，直到整张图都被遍历位置。与DFS一样，BFS也需要维护一个已遍历顶点的状态，否则会存在重复遍历，陷入死循环的情况。广度优先遍历的过程如图3所示。

深度优先遍历的伪代码结构描述如下：

// 无向图最短路径算法, 从s开始广度优先遍历整张图 LinkedList<Integer> q = new LinkedList<Integer>(); q.push( s ); visited[s] = true; ord[s] = 0; while( !q.isEmpty() ){ int v = q.pop(); for( int i : G.adj(v) ) if( !visited[i] ){ q.push(i); visited[i] = true; from[i] = v; ord[i] = ord[v] + 1; } }