C++数据结构-图的知识扩展部分：连通图、生成树及顺序存储结构

1、连通图

在之前的讨论中提到过，在图论中我们探讨了两个顶点之间的可达性问题。具体而言，在某些情况下尽管V1和V3之间没有直接连接（即它们没有边直接相连），但仍然可以通过多条不同的路径实现它们之间的通信或关系建立。这些不同的路径组合展示了网络结构中的复杂性和多样性。

V1-V2-V3 和 V1-V4-V3 ，因此称 V1 和 V3 之间是连通的。

图 1 顶点之间的连通状态示意图

在无向图中，如果任意两个顶点之间都存在连通路径，则称此无向图为连通图。例如，在如图2所示的无向图中就是一个典型的连通图实例，在该图中任意两顶点之间都存在连通路径。

图 2 连通图示意图

若无向图并非连通，则该子图具备连通性的特征，则称此子图为一个连通分量。

在之前的内容中提到，在某张图表中选取了部分顶点和边所形成的图形是该图表的一个子集构成的新图形；值得注意的是，在这里讨论的"子 图"特指其中最大