数据结构（七）：图

定义

图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

定义来自维基百科:图论

结构

图中只包含两种类型的元素：顶点（vertex）和边（edge），所以图可以由顶点集合和边集合进行表示，即：。根据边是否具有方向，可以将图分为有向图和无向图两种。

无向图

graph

有向图

digraph

上面两张图 graph 和 digraph 具有相同的顶点集合 ，但是边集合 不同，所以属于不同的两个图。

权重

上述图定义中提到，边的作用是用来描述两个顶点之间的关系，图 graph 和 digraph 两个示例中的边仅能表示两个顶点之间是连通的，可达的，并不能代表别的意义。可以给边设置大小值，即权重，表示两个顶点之间连通的程度。例如当图中顶点表示城市的坐标时，则可以设置连接两个顶点的边的权重为距离，或某种交通方式消耗的时间。

graph

度

从一个顶点出发，到相邻顶点的边的个数称为该顶点的出度，以该顶点为终点的边的个数称为该顶点的入度。因为无向图的边不具有方向性，所以无向图中顶点的出度与入度相等。

路径与回路

从顶点集合 中选择 作为起点， 作为终点，从起点出发到达终点的过程中，经过的边的集合称为路径，路径中边的个数称为路径长度。若路径中不重复经过一个顶点，则称为简单路径。若起点和终点是同一个顶点，则该路径也称之为回路。

连通图、连通分量与生成树

对于无向图，若图中任意两个顶点之间存在路径，则该无向图为连通图；对于有向图，若图中任意两个顶点之间存在路径，则该有向图为强连通图。

对于无向图，其极大连通子图称为该无向图的连通分量；对于有向图，其极大强连通子图称为该无向图的强连通分量。

根据连通分量定义可知，对于连通图，极大连通子图是其自身，所以图的连通分量就是其自身。对于非连通图，因为可以存在多个极大连通子图，所以可以具有多个连通分量。

连通图的最小连通子图也称之为生成树，即包含顶点集合 ，但是边的个数为 。生成树可以有多个，经常提到的最小生成树，也就是带权连通图中权值之和最小的生成树。

图相关的概念较多，再次强调一点，就像在介绍二叉树时所说，概念只是起到辅助说明的角色，为了方便理解和传播事物而诞生的产物，不应该过分纠结概念而忽略了真正的目的。