C++ 图的基本概念

zltzlt

C++ 图的基本概念

图有多个结点，而且每一个结点可以连接多个其他结点。

线性表中的元素是 “一对一” 的关系，树中的元素是 “一对多” 的关系，图中的元素是 “多对多” 的关系。

无向图

无向图 G 由一个顶点集 V 和一个边集 E 组成，通常记作 G = (V, E) 。

用 (v, w) 表示从顶点 v 到顶点 w 的一条边。

图中的顶点即为数据结构中的数据元素，边集实际上是定义在顶点集上的一个关系。

例如，描述下面这张无序图：



顶点集 V = {v1, v2, v3, v4, v5}

边集 E = {(v1, v2), (v1, v3), (v1, v4), (v2, v5), (v4, v5)}

有向图

存在单项关系（即方向性）的图叫做有向图。

有向图 G 由一个顶点集 V 和一个弧集 E 组成，通常记作 G = (V, E) 。

和无向图一样，顶点即元素，弧集是关系。

用有序对 <v, w> 表示从顶点 v 到顶点 w 的一条弧。

例如，描述下面这张有序图：


顶点集 V = {a, b, c, d}

边集 E = {<a, b>, <a, c>, <b, c>, <b, d>, <c, d>}