7.4 图的连通性问题

01

无向图的连通分量和生成树

1、在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。

2、对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

02

有向图的强连通分量

1、深度优先搜索是求有向图的强连通分量的一个新的有效方法。

2、在有向图G上，从某个顶点出发沿以该顶点为尾的弧进行深度优先搜索遍历，并按其所有邻接点的搜索都完成的顺序将顶点排列起来。

3、在有向图G中，从最后完成搜索的顶点出发，沿着以该顶点为头的弧作逆向的深度优先搜索遍历，若此次遍历不能访问到有向图中所有顶点，则从余下的顶点中最后完成搜索的的那个顶点出发，继续作逆向的深度优先搜索遍历，一次类推，直至有向图中所有顶点都被访问到为止。

03

最小生成树

1、构造最小生成树可以有多种算法，其中多数算法利用了最小生成树的一种称为MST的性质。

2、普利姆算法和克鲁斯卡尔算法是两个利用MST性质构造最小生成树的算法。

04

关节点和重连通分量

1、假若在删除顶点以及顶点相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，称顶点为该图的一个关节点。

2、一个没有关节点的连通图称为是重连通图。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！