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

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

图1. 原始图

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

图2. 深度优先遍历 DFS

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

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

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

图3. 广度优先遍历 BFS

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

// 无向图最短路径算法, 从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;
        }
}