数据结构（六）——无向图_无向连通图是什么

含有平行边（连接同一对顶点的两条边）的图称为多重图，而将没有平行边或自环（一条连接一个顶点及其自身的边）的图称为简单图。

1.1 术语

某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集（以及它们所依附的所有顶点）组成的图。

在图中，路径是由边顺序组成的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含重复顶点（除了起点和终点）和边的环。路径或者环的长度为其中包含的边数。

当两个顶点存在一条连通双方的路径时，称这两个点是连通的。

如果从任意一个顶点都存在一条路径到达任一个任意节点，称为连通图。一个非连通的图由若干个连通的部分组成，它们都是极大连通子图。

树是一个无环连通图。互不相连的树组成的集合称为森林。连通图生成树是它的一个子图，它含有图中所有顶点且是一棵树。图的生成树森林是它所有连通子图的生成树集合。

当且仅当一个含有V个节点的图G含有以下条件之一时，它就是一棵树：

G有V-1条边且不含有环。

G有V-1条边且是连通的。

G是连通的，但删除一条边都会使它不再连通。

G是无环图，但添加任意一条边都会产生一个环。

G中任意一个顶点之间仅存在一条简单路径。

图的密度是已经连接的顶点对占所有可能被连接的顶点对的比例。

二分图是一种能够将所有节点分为两部分的图，其中图的每条边所连接的两个顶点都分别属于不同的部分。

1.2 深度优先搜索（DFS）