图的基本概念

图是由一组顶点（vertex）和一组能够将两个顶点相连的边（edge）组成的。

一般使用0至V-1来表示一张含有V个顶点的图的各个顶点。这样约定是为了方便使用数组的索引来编写能够高效访问各个顶点中信息的代码。一般使用v-w的记法来表示连接v和w的边。

特殊的图

• 自环，即一条连接一个顶点和其自身的边；
• 平行边（多重图），连接同一对顶点的两条边。

相关术语

当两个顶点通过一条边相连时，我们称这两个顶点是相邻的，并称这条边依附于这两个顶点。某个顶点的度数即为依附于它的边的总数。子图是由一幅图的所有边的一个子集组成的图。路径是由边顺序连接的一系列顶点。简单路径是一条没有重复顶点的路径。环是一条至少含有一条边且起点和终点相同的路径。简单环是一条不含有重复顶点和边的环。路径或者环的长度为其中所包含的边数。

当两个顶点之间存在一条连接双方的路径时，我们称一个顶点和另一个顶点是连通的。我们用类似u-v-w-x的记法来表示u到x的一条路径，用u-v-w-x-u表示从u到v到w到x再回到u的一条环。

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

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

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

1. G有V-1条边且不含有环；
2. G有V-1条边且是连通的；
3. G是连通的，但删除任意一条边都会使它不再连通；
4. G是无环图，但添加任意一条边都会产生一条环；
5. G中任意一对顶点之间仅存在一条简单路径。

图的密度是指已经连接的顶点对占所有可能被连接的顶点对的比例。在稀疏图中，被连接的顶点对很少，在稠密图中，只有少部分顶点对之间没有边连接。

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

二分图图示