【图(上)】图的遍历，深度优先，广度优先

深度优先搜索(Depth First Search, DFS)

类似于树的先序遍历 先将根节点设置成已经访问过，对根节点的每一个邻接点，选取一个，查看有没有访问过，没有访问，设置成访问，并将此节点作为根结点，重复上述步骤；如果所有邻接点都已经访问过，放回到上一步的根节点中，查看是否有没有访问的邻接点，直到返回到第一步的根节点中。

void DFS(Vertex V) { visited[V] = true; for (V 的每个邻接点W) if (!visited[W]) DFS(W); }

若有N个顶点、E条边，时间复杂度是：

用邻接表存储图，有O(N+E)用邻接矩阵存储图，有O(N²)

广度优先搜索(Breadth First Search, BFS)

类似于树的层序遍历，先将一个元素压入队列之中，设置该元素为已访问，每次从队列取出一个元素，并将该元素所有未访问的邻接点元素压入队列中，直到队列为空，每次压入队列，将该元素设置为已经访问。

void BFS(Vertex V) { visited[V] = true; Enqueue(V, Q); while (!IsEmpty(Q)) { V = Dequeue(Q); for (V 的每个邻接点W) if (!visited[W]) { visited[W] = true; Enqueue(W, Q); } } }

若有N个顶点、E条边，时间复杂度是：

用邻接表存储图，有O(N+E)用邻接矩阵存储图，有O(N²)

为什么需要两种遍历？ 小人从开始的地方找到绿色的出口，白色可以通过，黑色堵住了，可以对角线走，图中小人出现的地方为访问过的结点，可以看到不同的搜索访问的复杂度时不一样的。

图不连通怎么办？

连通：如果从V到W存在一条（无向）路径，则称V和W是连通的

路径：V到W的路径是一系列顶点{V, v₁, v₂, …,v_n, W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。如果V到W之间的所有顶点都不同，则称简单路径

回路：起点等于终点的路径

连通图：图中任意两顶点均连通

连通分量：无向图的极大连通子图

极大顶点数：再加1个顶点就不连通了极大边数：包含子图中所有顶点相连的所有边

强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的

强连通图：有向图中任意两顶点均强连通

强连通分量：有向图的极大强连通子图

void DFS(Vertex V) { visited[V] = true; for (V 的每个邻接点W) if (!visited[W]) DFS(W); } void ListComponents(Graph G) { for (each V in G) if (!visited[V]) DFS(V); /*or BFS( V )*/ }