连通图

连通图

图还有一些有关路径的术语：

• 连通：如果从顶点V到W存在一条路径，则称V和W是连通的。

• 路径：顶点V到W的路径是有序顶点序列$(V, v_1, v_2, \dots, v_n, W)$，其中任意一对相邻的顶点间都有图中的边。

• 路径长度：路径中边的个数，如果是带权图（网络），则是所有边的权重和。

• 简单路径：顶点V到W之间的路径中所有顶点都不同。

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

如果无向图中任意两顶点均连通，那么称这个图是一个连通图。

一个图的连通分量指的是图的极大连通子图，极大连通子图需要满足两点要求：

1. 顶点数达到极大，即再加一个顶点就不连通了。

2. 边数达到极大，即包含子图中所有顶点相连的所有边。

对于有向图而言，如果有向图中任意一对顶点V和W之间存在双向路径，既可以从$V$走到$W$，也可以从$W$走到$V$，但这两条路径不一定是同一条，则称该图为强连通图。

如果有向图不是强连通图，但将所有的有向边替换为无向边之后可以变为连通图，则称该图为弱连通图。

有向图的极大强连通子图称为强连通分量。

非连通图的遍历

如果一个图不是连通图，那么无论使用深度优先遍历还是广度优先遍历，都会有顶点无法被访问到。解决这个问题的方式是每调用一次dfs(V)或bfs(V)，就把顶点V所在的连通分量遍历一遍。

非连通图的深度优先遍历

dfs(Vertex V)
    isVisited[V] = true
    for v in neighbors(V)
        if !isVisited[v]
            DFS(v)

listComponents(Graph G)
    for V in vertices(G)
        if !isVisited[V]
            DFS(V)