A
B
A
B
C C D E D
图7.1 无向图G1
图7.2 有向图G2
2. 有向图
在一个图中，如果连接任意2个顶点的是一条弧 <vi ,vj>，即顶点之间的连线是有方向的，则称该图为有 向图。对于弧<vi ,vj>，vi 被称为起点（弧尾），vj 被称 为终点（弧头）。如图7.2。 G1=(V1, E1) V1={A,B,C,D} E1={<A,B>, <A,C>, <C,D>, <D,A>, <D,C>}
1.2 图的相关术语
1. 无向图
在一个图中，如果连接任意2个顶点的是一条无向边 (vi ,vj)，即顶点之间的连线是无方向的，则称该图为无向 图。如图7.1。 G1=(V1, E1) V1={A,B,C,D,E} E1={(A,B), (A,D), (B,C), (B,E), (C,D), (C,E)}
数据结构
（数据结构及其算法）
冯耀霖
Chap 7
图
图的基本概念 概念
▲图的定义 ▲图的相关术语 ▲图的基本操作
图（graph）是一种复杂的数据结构，它能够为解 决许多具体问题提供非常理想的非数值数学模型。当今， 图结构已广泛应用于计算机科学、系统工程、管理工程、 通信与网络理论、自动控制、运筹学以至社会科学等诸 多学科。 图形结构所研究的图并非生活中所说的图画或地图， 而是用一些点和线来表示事物之间关系的某种抽象模型， 本质上是数据集合与其上关系的图形表示。
7. 权（weight）
与图的边或弧相关的数值，用于表示从一个顶点到另 一个顶点的距离、所需的时间或花费的代价等。
图7.3 彼得森图
