图的遍历

由于图中可能存在网状结构，所以需要一个辅助数组 visited[] 来记录顶点是否被访问过。

深度优先搜索

是一个递归定义的算法，需要栈作为辅助数据结构，有回溯。

深度优先生成树

广度优先搜索

BFS 是一个分层遍历的算法，没有回溯，需要用一个队列作为辅助数据结构。

单源最短路径

BFS 可以用于解决「非带权图」的单源最短路径问题。

广度优先生成树

图的连通行

可以通过图的遍历算法来检验图的连通性。

对于无向图：如果一次遍历可以访问所有节点，那么图是连通的
对于有向图：如果图不是「强连通的」，那么对一个连通分量进行遍历的时候，可能无法访问到所有的节点