数据结构的C++实现之图的定义和术语总结

一、图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V 是图G中顶点的集合，E是图G中边的集合。在图中的数据元素，我们称之为顶点（Vertex），顶点集合有穷非空。在图中， 任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

二、图按照有无方向分为无 向图和有向图。无向图由顶点和边组成，有向图由顶点和弧构成。弧有弧尾和弧头之分，带箭头一端为弧头。

三、 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫做完全图，有向的叫有向完全图。若无重复的边 或顶点到自身的边则叫简单图。

四、图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度。有向图顶点 分为入度和出度。

五、图上的边或弧带有权则称为网。

六、图中顶点间存在路径，两顶点存在路径则说明是 连通的，如果路径最终回到起始点则称为环，当中不重复的叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向 则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量。

七、无向图中连通且n 个顶点n-1条边称为生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森 林。