第六章 图.

Presentation on theme: "第六章 图."— Presentation transcript:

1 第六章 图

2 6.1 图的基本概念 6.2 图的存储表示 6.3 图的遍历 6.4 图的应用

3 在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置 n(n-1)/2 条线路，那么，如何在这些可能的线路中选择 n-1 条，以使总的耗费最少呢？
6 5 1 2 4 5 5 3 3 6 2 4 5 6 6

4 图（Graph）是一种较线性表和树更为复杂的非线性结构。
在线性结构中，结点之间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继。 在树形结构中，结点之间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）。 在图结构中，对结点（图中常称为顶点）的前趋和后继个数都是不加限制的，即结点之间的关系是任意的。图中任意两个结点之间都可能相关。 由此，图的应用极为广泛，特别是近年来的迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。

5 6.1 图的基本概念 6.1.1 图的结构定义: 图是由一个顶点集 V 和一个弧集 E构 成的数据结构 G = (V , E )
6.1 图的基本概念 图的结构定义: 图是由一个顶点集 V 和一个弧集 E构 成的数据结构 G = (V , E ) 其中， V={ vi| vi ∈某个数据元素集合} E={(vi,vj)| vi,vj ∈V且P(vi,vj)} 或E={<vi,vj>| vi,vj ∈V且P(vi,vj)}。 其中，G表示图, V是顶点的集合，E是边或弧 的集合。在集合E中，P(vi,vj)表示顶点vi和顶 点vj之间有边或弧相连。

6 在图(a)中， V = {V1，V2，V3，V4，V5}，
E = {(V1，V2)，(V2，V3)，(V1，V5)，(V2，V4)，(V4，V5)}； 在图(b)中，V = {V1，V2，V3，V4，V5}， E={<V1, V2>, <V1, V4>, <V5, V2>, <V4, V3>, <V4, V5>}。

7 6.1.2 图的基本术语 有向图、无向图、权、网、子图 完全图、稀疏图、稠密图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路
图的基本术语 有向图、无向图、权、网、子图 完全图、稀疏图、稠密图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路 连通图、连通分量、 强连通图、强连通分量 生成树、生成森林

8 若<v, w>VR, <v,w>表示从 v 到 w 的一条弧，并称 v 为弧尾或初始点，w 为弧头或终端点,“弧”是有方向的。因此称由顶点集和弧集构成的图为有向图。
例如: G1 = (V1, VR1) 其中 V1={A, B, C, D, E} VR1={<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> } A B E C D

9 若VR是对称的，即<v, w>VR 必有<w, v>VR, 以无序对 (v,w) 代替这两个有序对,表示顶点 v 和顶点 w 之间的一条边,此时的图称为无向图。
由顶点集和边集构成的图称作无向图。 例如: G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={( A,B ), ( A,E ), ( B,E ), ( C,D ), ( D,F ), ( B,F ), ( C,F ) } B C A D F E

10 有时图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。
弧或边带权的图分别称为网。 A B E C F 15 9 7 21 11 3 2

11 A E F B C A B E C F 假设有两个图 G=(V,VR) 和 G=(V,VR)
如果 VV, VRVR，则称 G 为 G 的子图。 A E F B C A B E C F 图 G 图 G’

12 例： 假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条弧的无向图称作完全图；
3 无向完全图 2 1 3 有向完全图 例： 若边或弧的个数 e<nlogn，则称作稀疏图， 否则称作稠密图。

13 对无向图来说 A C D F E B 例如: TD(B) = 3 TD(A) = 2
假若顶点v和顶点w 之间存在一条边，则称顶点v和w互为邻接点； 和顶点v 关联的边的数目定义为顶点v的度，记为TD（V）。 A C D F E B 例如: TD(B) = 3 TD(A) = 2

14 对有向图来说 A B E C F 例如: 若<v, w>VR,则称自顶点v邻接到顶点w。
以顶点v为弧尾的弧的数目称为v的出度,记为OD（v）。以顶点v为弧头的弧的数目称为v的入度,记为ID（v）。 顶点的度(TD)=出度(OD)+入度(ID) A B E C F 例如: OD(B) = 1 ID(B) = 2 TD(B) = 3

15 A B E C F 图G=(V,{VR})中顶点u 到顶点w 之间存在一条路径（在有向图中路径也是有向的）。路径上边的数目称作路径长度。
简单路径: 序列中顶点不重复出现的路径。 回路(或环): 序列中第一个顶点和最后一个顶点相同的路径。 简单回路: 除序列中第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路。 A B E C F 例： A,B,C,F是A到F，长度为3的路径。 B,C,F,B是回路

16 例 2 4 5 1 3 6 G1 路径：1，2，3，5，6，3 路径长度：5 简单路径：1，2，3，5 回路：1，2，3，5，6，3，1 简单回路：3，5，6，3 例 1 5 7 3 2 4 G2 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

17 无向图G中，若从顶点v到顶点w有路径，则称v和w是连通的；若图G中任意两个顶点之间都有路径相通，则称此图为连通图；否则，称之为非连通图。
B A C D F E B A C D F E 连通图 非连通图

18 若对于每一对v,wV，v=w，从v到w和从w到v都存在路径，则称此有向图为强连通图。
对有向图G， A B E C F A B E C F 强连通图

19 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。
一棵有N个顶点的生成树有且仅有N-1条边，但有N-1条边的图不定是生成树。 B A C D F E B A C D F E 连通图 连通图的生成树

20 例 2 1 3 有向完全图 无向完全图 3 5 6 例 2 4 1 图与子图 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4

21 例 2 4 5 1 3 6 连通图 3 5 6 例 强连通图

22 6.1.3 抽象数据类型图的定义 图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。图的抽象数据类型定义如下： ADT Graph{
抽象数据类型图的定义 图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。图的抽象数据类型定义如下： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合， 称为顶点集。 数据关系R: R={VR} VR={<v,w>| v,w∈v且P(v,w)，<v,w> 表示 从v 到w 的弧，谓词P(v,w)定义了弧<v,w> 的意义或信息。 基本操作P: ………… }ADT Graph

23 基本操作 结构的建立和销毁 对顶点的访问操作 插入或删除顶点 插入和删除弧 对邻接点的操作 遍历

24 结构的建立和销毁 CreatGraph(&G, V, VR): // 按定义(V, VR) 构造图 DestroyGraph(&G):
// 销毁图

25 对顶点的访问操作 LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在
// 图中“位置” ；否则返回其它信息。 GetVex(G, v); // 返回 v 的值。 PutVex(&G, v, value); // 对 v 赋值value。

26 对邻接点的操作 FirstAdjVex(G, v); NextAdjVex(G, v, w);
// 若w是v的最后一个邻接点，则返回“空”。

27 插入或删除顶点 InsertVex(&G, v); DeleteVex(&G, v); // 删除G中顶点v及其相关的弧。

28 插入和删除弧 InsertArc(&G, v, w); // 在G中增添弧<v,w>，若G是无向的，
// 则还增添对称弧<w,v>。 DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>。

29 遍 历 DFSTraverse(G, v, Visit()); BFSTraverse(G, v, Visit());
遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。

30 6.2 图的存储结构 邻接矩阵 邻接表 十字链表

31 邻接矩阵 用两个数组分别存储： （1）数据元素(顶点)的信息 （2）数据元素之间的关系(边或弧)的 信息即邻接矩阵。

32 邻接矩阵: 表示结点间相邻关系的矩阵，用一个二维数组来表示集合E。此二维数组称为邻接矩阵。 若G是一个具有n个结点的图，其邻接矩阵是一个n阶方阵。

33 无向图的邻接矩阵 定义 A[i][j]=A[j][i]=
设G=(V,E)是有n(n ≥ 1)个顶点的无向图，则G的邻接矩阵是一个n×n 矩阵: 1 (vi,vj) VR A[i][j]=A[j][i]= 0 (vi,vj) VR

34 邻接矩阵第i行（或第i列）的元素之和则是顶点Vi的度。
V3 V4 V5 无向图的邻接矩阵为对称方阵； 邻接矩阵第i行（或第i列）的元素之和则是顶点Vi的度。

35 有向图的邻接矩阵 定义 设G=(V,VR)是有n(n≥1)个顶点的有向图，G的邻接矩阵是具有如下性质的n×n方阵: A[i][j]=
1 当 <vi,vj>  VR 0 当 <vi,vj>  VR

36 邻接矩阵第i行的元素之和为顶点Vi的出度；邻接矩阵第j列的元素之和为顶点Vj的入度。
V1 V2 V3 V4 有向图的邻接矩阵为非对称矩阵； 邻接矩阵第i行的元素之和为顶点Vi的出度；邻接矩阵第j列的元素之和为顶点Vj的入度。 网的邻接矩阵见书 P161

37 Wij 若(Vi, Vj)或< Vi, Vj >是E(G)中的边或弧
A[i][j]= 0或∞ 若(Vi, Vj)或< Vi, Vj >不是E(G)中的边或弧 邻接矩阵中，Wij表示边(vi，vj)或弧<vi，vj>上的权值；∞表示一个计算机允许的大于所有边上权值的数。

38 图的邻接矩阵存储表示： #define INFINITY INF_MAX // 最大值∞ #define MAX_VERTEX_NUM 20
// 最大顶点个数 Typedef enum {DG,DN,AG,AN} GraphKind; // {有向图，有向网，无向图，无向网}

39 typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型，
// 对无权图，用1或0表示相邻否，对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix [MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

40 typedef struct { // 图的定义 VertexType vexs[MAX_VERTEX_NUM];
// 顶点向量 AdjMatrix arcs; // 邻接矩阵 int vexnum, arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 } MGraph;

41 特点： 借助于邻接矩阵，容易判定任意两个顶点之间是否有边（或弧）相连，并容易求得各个顶点的度。
对于无向图，顶点Vi 的度是邻接矩阵第i 行（或第i列）的元素之和。 对于有向图，第i 行的元素之和为顶点Vi 的出度；第j 列的元素之和为顶点Vj的入度。 占用的存储单元个数只与图中结点个数有关，而与边的数目无关。

42 邻接表是图的一种顺序存储与链式存储相结合的存储结构，类似于树的孩子链表法。
图的邻接表

43 顶点信息通常以顺序结构的形式存储，以便随机访问任一顶点的邻接点链表，由两个域组成：
data fristarc data—存贮顶点vi名或其它有关信息的数据； fristarc — 指向vi的第一个邻接点的指针。

44 在邻接表中，对图的每个顶点Vi建立一个单链表，单链表中的结点表示依附于顶点的边。链表中每个结点由三个域组成：
adivex nextarc info Adivex（邻接点域） — 与顶点vi邻接的点在图中 的位置 Nextarc（链域）—与顶点vi邻接的点的下一条一条边或弧的结点 Info（数据域）—存贮与边和弧相关的信息,如权值等

45 图的结构定义 typedef struct { AdjList vertices; // 表头结点向量
int vexnum, arcnum; // 图的当前顶点数和弧数 int kind; // 图的种类标志 } ALGraph;

46 弧的结点结构 adjvex nextarc info typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条边或弧的指针 InfoType *info; // 该弧相关信息的指针 } ArcNode;

47 顶点的结点结构 data firstarc typedef struct VNode { VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_VERTEX_NUM];

48 1、无向图的邻接表 2、有向图的邻接表 3、有向图的逆邻接表

49 无向图的邻接表 在无向图的邻接表中，顶点Vi的度恰为第i个链表中的结点数.      1 2 3 4 3 1 4 2 4 3 1
1 2 3 4 V1 3 1  V1 V2 V4 V3 V5 V2 4 2  V3 4 3 1  V4 2  V5 2 1  在无向图的邻接表中，顶点Vi的度恰为第i个链表中的结点数.

50 有向图的邻接表 有向图的邻接表中，第i个链表中的结点个数是顶点Vi的出度。 在有向图的邻接表中不易找到指向该顶点的弧。     1
1 2 3 V1 2 1  V2  V3 3  V4  V3 V4 有向图的邻接表中，第i个链表中的结点个数是顶点Vi的出度。 在有向图的邻接表中不易找到指向该顶点的弧。

51 有向图的逆邻接表 有向图的逆邻接表中，第i个链表中的结点个数是顶点Vi的入度。 在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。
1 2 3 V1 3  V2  V3  V3 V4 V4 2  有向图的逆邻接表中，第i个链表中的结点个数是顶点Vi的入度。 在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。

52 优点： 缺点： 在边稀疏(e<<n(n-1)/2)的情况下，用邻接表比邻接矩阵节省存储空间；
运算方便，容易找到任意顶点的第一个邻接点和下一个邻接点。 缺点： 要判定任意两个顶点之间是否有边或弧相连时，则需扫描第i个或第j个链表，不及邻接矩阵方便。

53 6.3 图的遍历 从图中某个顶点出发，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程，叫做图的遍历。

54 图的遍历要比树的遍历复杂得多。因为图中任一顶点都可能和其余的顶点相邻接。所以，在访问了某个顶点之后，可能沿着某条搜索路径又回到该顶点上。为了避免同一顶点被多次访问，在遍历图的过程中，必须记下每个已访问过的顶点。为此，我们可设一个辅助数组visited[0..n-1]，它的初始值置为“假”或者“0”，一旦访问了顶点Vi，便置visited[i]为“真”或者被访问时的次序号。

55 通常有两条遍历图的路径： 深度优先搜索（纵向优先搜索） 广度优先搜索（横向优先搜索）

56 1、深度优先搜索 遍历类似于树的先根遍历,是树的先根遍历的推广 假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先遍历图，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。

57 V1 V2 V3 V4 V5 V6 V7 V8 深度优先搜索结果： V1 → V2 → V4 → V8 → V5 → V3 → V6 → V7

58

59 例 A B L M C F D E G H K I J A L M J B F C D E G I K H

60 V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V5 V6 V3 V7

61 深度遍历：V1 V2 V4  V8 V5 V6 V3 V7
例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍历：V1 V2 V4  V8 V5 V6 V3 V7

62 算法6.1 // 算法使用全局变量 int visited[MAX]; //访问标志数组 Status(*VisitFunc)(int v); // 函数变量 void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 对图G作深度优先遍历。 VisitFunc = Visit; for (v=0; v<G.vexnum; ++v) visited[v] = 0; // 访问标志数组初始化 if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS }

63 算法6.2 void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G visited[v]=1; VisitFunc (v) ; //访问第v个顶点 for(w=FirstAdjVex(G, v);w>=0; w=NextAdjVex(G, v,w)) if(!visited[w]) DFS(G,w) ; //对v的尚未访问的邻接顶点w递归调用DFS }

64 从上页的图解可见: 1. 深度优先搜索遍历连通图的过程类似于树的先根遍历； 2. 如何判别V的邻接点是否被访问？
解决的办法是：为每个顶点设立一个 “访问标志 visited[w]”。

65 2、广度优先搜索 遍历类似于树的按层次遍历过程
从图中的某个顶点V0出发，并在访问此顶点之后，依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

66 广度优先搜索结果： V1 → V2 → V3 → V4 → V5 → V6 → V7 → V8 V1 V2 V3 V4 V5 V6 V7

67

68 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8
例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

69 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8
例 V1 V2 V4 V5 V3 V7 V6 V8 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

70 广度优先搜索图的过程，类似于树的按层次遍历是以v为起始点，由近至远，依次访问和v有路径相通且路径长度为1，2，……的顶点。
和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储以被访问的路径长度为1，2，…的顶点。

71 6.4 图的应用 V1 1、（1）连通图 从无向图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可遍历完图中所有顶点，这个图就是连通图。

72 这3个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图的3个连通分量。
（2）对非连通图 A B L M C F D E G H K I J A L M J B F C D E G I K H 这3个顶点集分别加上所有依附于这些顶点的边，便构成了非连通图的3个连通分量。

73 2、图的生成树 （1）设G=(V,E)是个连通图，而E(G)为连通图中所有边的集合，若从图中任一顶点开始作一次搜索过程，则将E(G)分成两个集合：T(G)和B(G)。 T(G)是遍历图时走过的边的集合， B(G)是剩余边的集合。 T(G)和图中所有顶点一起构成连通图G的极小连通子树，称为图G的生成树。 图的生成树不唯一，从不同结点出发进行搜索，可以得到不同的生成树。

74 深度优先生成树：由深度优先搜索得到的生成树。 广度优先生成树：由广度优先搜索得到的生成树。
1 1 1 2 3 2 3 2 3 4 5 6 7 4 5 6 7 4 5 6 7 8 8 8 无向图 深度优先生成树 广度优先生成树

75 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7
例 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8

76 例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8 广度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8

77 （2）对于非连通图： 连通分量的生成树组成非连通图的生成森林 深度优先生成森林 A B L M C F D E G H K I J A B

78 3.最小生成树： 任何具有n个顶点的连通图，构成（1）至少有n-1条边，而且所有具有n-1条边的连通图都是树。若连通图的各条边赋以权值表示相应的代价，那么,一棵生成树的代价就是树上各边的代价之和。 从连通图中的生成树中选择一棵代价最小的生成树，该生成树叫做最小生成树。

79 由最小生成树的定义可知，构造有n个顶点的无向连通网的最小生成树必须满足以下三个条件：
(3) 构造的最小生成树中不存在回路。

80 问题背景： 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？

81 在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。n个城市之间，最多可能设置 n(n-1)/2 条线路，那么，如何在这些可能的线路中选择 n-1 条，以使总的耗费最少呢？
6 5 1 2 4 5 5 3 3 6 2 4 5 6 6

82 分析问题（建立模型）： 可以用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中，网的顶点表示城市，边表示两城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通讯网。现在，我们要选择这样一棵生成树，也就是总的耗费最少。这个问题就是构造连通网的最小代价生成树 (简称为最小生成树)的问题。一棵生成树的代价就是树上各边的代价之和。

83 问题等价于： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。 算法一：普里姆 (Prim) 法 算法二：克鲁斯卡尔 (Kruskal) 法

84 普里姆算法的基本思想: 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。
图上顶点分成两个集合：已落在生成树上的顶点集 U 和未落在生成树上的顶点集V-U ， 在所有连通U和V-U中顶点的边中选取权值最小的边并入集合U中。

85 例如: a a b b c c e e g g d d f f = 14+8+3+5+16+21 = 67 19 5 5 12 14 14
18 e e 8 8 16 16 3 3 g g d d 27 21 21 f f 所得生成树权值和 = = 67

86 VertexType adjvex; // U集中的顶点序号 VRType lowcost; // 边的权值
设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： struct { VertexType adjvex; // U集中的顶点序号 VRType lowcost; // 边的权值 } closedge [MAX_VERTEX_NUM];

87 克鲁斯卡尔算法的基本思想： 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

88 例如: 19 19 a a b b 5 5 12 12 14 14 c c 7 7 18 18 e e 16 16 8 8 3 3 g g d d 27 21 21 f f

89 5 a b 14 c 8 3 e 16 d g 21 f