2
第 6 章 图
6.1 图的基本概念
图 (G) 是一种非线性数据结构，它由两个集合 V(G) 和 E
(G) 组成，形式上记为 G=(V ， E) 。其中， V(G) 是顶点 (Ve
rtex) 的非空有限集合； E(G) 是 V(G) 中任意两个顶点之间的
关系集合，又称为边 (Edge) 的有限集合。
3
第 6 章 图
当 G 中的每条边有方向时，则称 G 为有向图。有向边
通常用由两个顶点组成的有序对来表示，记为〈起始顶点，
终止顶点〉。有向边又称为弧，因此，弧的起始顶点就称为
弧尾；终止顶点称为弧头。例如，图 6-1(a) 给出了一个有向
图的示例，该图的顶点集和边集分别为
V(G
1
)={A, B, C}
E(G
1
)={<A, B>, <B, A>, <B, C>, <A, C>}
4
第 6 章 图
图 6-1 有向图和无向图示例
5
第 6 章 图
若 G 中的每条边是无方向的，则称 G 为无向图。这时
两个顶点之间最多只存在一条边。无向边用两个顶点组成的
无序对表示，记为 ( 顶点 1 ，顶点 2) 。图 6-1(b) 给出了一个
无向图的示例，该图的顶点集和边集分别为
V(G
2
)={ A, B, C }
E(G
2
)={(A, B), (B, C), (C, A)}
={(B, A), (C, B), (A, C)}
在下面讨论的图中，我们不考虑顶点到其自身的边，也
不允许一条边在图中重复出现，如图 6-2 所示。
