数据结构（七）（图）数据结构（七）：图

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

定义来自维基百科:图论

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

文章图片
graph 有向图

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

文章图片
graph 度从一个顶点出发，到相邻顶点的边的个数称为该顶点的出度，以该顶点为终点的边的个数称为该顶点的入度。因为无向图的边不具有方向性，所以无向图中顶点的出度与入度相等。
路径与回路从顶点集合中选择作为起点，作为终点，从起点出发到达终点的过程中，经过的边的集合称为路径，路径中边的个数称为路径长度。若路径中不重复经过一个顶点，则称为简单路径。若起点和终点是同一个顶点，则该路径也称之为回路。
连通图、连通分量与生成树对于无向图，若图中任意两个顶点之间存在路径，则该无向图为连通图；对于有向图，若图中任意两个顶点之间存在路径，则该有向图为强连通图。
对于无向图，其极大连通子图称为该无向图的连通分量；对于有向图，其极大强连通子图称为该无向图的强连通分量。
根据连通分量定义可知，对于连通图，极大连通子图是其自身，所以图的连通分量就是其自身。对于非连通图，因为可以存在多个极大连通子图，所以可以具有多个连通分量。
连通图的极小连通子图也称之为生成树，即包含顶点集合，但是边的个数为。生成树可以有多个，经常提到的最小生成树，也就是带权连通图中权值之和最小的生成树。