2. 设有两个图G=（V，{E}）和图G′=（V′，{E′}）, 若V′ 且E ′ V
G′为G的子图。 E, 则称图
2 4 5 3
1 3 6
5
6
图与子图
3. 邻接点 度 入度和出度 对于无向图 G=（V， {E}），如果边(v，v′)∈E， 则称顶 点v， v′互为邻接点，即v， v′相邻接。边(v, v′)依附 于顶点v和v’ ，或者说边(v,v’)与顶点v和v′相关联， 对于 有向图G=（V， {A}）而言，若弧<v，v′>∈A,则称顶点v邻 接到顶点v′，顶点v′邻接自顶点v，或者说弧<v， v′>与 顶点v和v′相关联。
1 3 2
5 4 G2
7 6
2 1
4 3 G1
5 6
顶点5的度：3 顶点2的度：4
顶点2入度：1 出度：3 顶点4入度：1 出度：0
4. 权与网 在实际应用中，有时图的边或弧上往往与具有一定意 义的数有关，即每一条边都有与它相关的数，称为权， 这些权可以表示从一个顶点到另一个顶点的距离或耗 费等信息。我们将这种带权的图叫做赋权图或网。
例 1 5 7
v
W 3 2 G2 4 6
图的基本操作
{结构初始化} CreateGraph(&G,
V, VR); 初始条件：V 是图的顶点集，VR 是图中弧 的集合。 操作结果：按 V 和 VR 的定义构造图 G。 {销毁结构} DestroyGraph(&G); 初始条件：图 G 存在。 操作结果：销毁图 G。

若<v，w>∈VR，则<v，w>表示从顶点v到顶点w的一条弧 （arc），并称v为弧尾（tail）或起始点，称w为弧头 （head）或终端点，此时图中的边是有方向的。若图中 的关系均为弧，则称这样的图为有向图。
例
v
W 1
2
4 3
5 6
G1
若<v，w>∈VR， 必有<w，v>∈VR，VR是对称关系，这时以无 序对（v，w）来代替两个有序对<v,w>和<w,v>，表示x和y之 间的一条边(edge)。若图中的关系均为边的关系，则此时的 图称为无向图。
2 2 1
1
3
3
对于无向图而言，顶点v 的度是指和v相关联边的数 目，记作TD（v）。 在有向图中顶点v的度有出度和入度两部分，其中 以顶点v为弧头的弧的数目成为该顶点的入度，记作ID （v），以顶点v为弧尾的弧的数目称为该顶点的出度， 记作OD（v）,则顶点v的度为TD（v）=ID（v）+ OD （v）。
第七章 图
7.1 7.2 7.3 7.4 7.5 7.6 图的定义和术语 图的存储结构 图的遍历 图的连通性问题 有向无环图及其应用 最短路径
学习目标

熟练掌握图中常用的术语和概念。 熟练掌握图的邻接矩阵和邻接表的存储方式并能熟练 运用这两种存储方法建立图的存储结构。 熟练掌握图的深度优先遍历和广度优先遍历的方法和 算法。 熟练掌握最小生成树的概念和算法。 掌握拓扑排序并能求出拓扑序列。 掌握最短路径算法并能求出最短路径。
7.1 图的定义和术语


图(Graph)是一种网状数据结构， 其形式化定义为 Graph =（V，R V={x|x∈DataObject}； R={VR} VR＝{<v,w>| v,w∈V且P(v,w)，<v,w>表示从v到w 的弧，谓词P(v,w)定义了弧<v,w>的意义或信息 } DataObject为一个集合，该集合中的所有元素具有相同的 特性。V中的数据元素通常称为顶点（vertex），VR是两 个顶点之间关系的集合。 P（x，y）表示x和y之间有特定的关联属性P。
2 1
4 3
5 6
路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3
1 3 2
5 4 G2
7 6
路径：1，2，5，7，6，5，2，3 路径长度：7 简单路径：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 简单回路：1，2，3，1
G4 无向图
2.二元组形式：
2
4
5
1 G1
3
6
G1 = （V，E） V(G1)={1,2,3,4,5,6} E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}
1
5
7
3
2 G2
4
6
G2 = （V，E） V(G2)={1,2,3,4,5,6,7} E(G1)={(1,2),(1,3),(2,3),(2,4), (2,5), (5,6), (5,7)}
5.

无向图G=（V，{E}）中从顶点v到v′的路径是一个顶 点序列vi0， vi1，vi2，…，vin，其中（vij-1，vij） ∈E，1≤j≤n。如果图G是有向图，则路径也是有向的， 顶点序列应满足<vij-1，vij>∈A， 1≤j≤n。路径的 长度是指路径上经过的弧或边的数目。在一个路径中， 若其第一个顶点和最后一个顶点是相同的，即v=v′， 则称该路径为一个回路或环。若表示路径的顶点序列 中的顶点各不相同，则称这样的路径为简单路径。除 了第一个和最后一个顶点外，其余各顶点均不重复出 现的回路为简单回路。

BFSTraverse(G, Visit()); 初始条件：图 G 存在，Visit 是顶点的应用函数。 操作结果：对图 G 进行广度优先遍历。遍历过程中对 每个顶点调用函数Visit 一次且仅一次。一旦 visit() 失败，则操作失败。
图的表示
1.逻辑图表示：如图G1和G2
G3 有向图
Hale Waihona Puke 图的基本术语
1. 完全图、稀疏图与稠密图
设n表示图中顶点的个数，用e表示图中边或弧的数目， 不 考虑图中每个顶点到其自身的边或弧。则：



对于无向图而言，其边数e的取值范围是0~n（n-1） /2。 我们称有n（n-1）/2条边（图中每个顶点和其余n-1 个顶点都有边相连）的无向图为无向完全图。 对于有向图而言，其边数e的取值范围是0~n（n-1）。 我们称有n（n-1）条边（图中每个顶点和其余n-1个顶点都 有弧相连）的有向图为有向完全图。 对于有很少条边的图（e<n logn）称为稀疏图， 反 之称为稠密图。