第六章 图（一）.

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

1 第六章 图（一）

2 复习 Huffman树的构造方法 Huffman编码基本规则

3 第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用
6.6 最短路径

4 本讲主要内容 理论： 主要讲解图的定义和术语、图的存储结构。 实验： 建立无向图（有向图）的邻接矩阵和邻接表算法。

5 6.1 图的定义和术语 图(Graph)：图G是由两个集合V(G)和E(G)组成的,记为G=(V,E) 其中：V(G)是顶点的非空有限集
有向图：E(G)是有向边（也称弧）的有限集合，弧是顶点的有序对，记为<v,w>，v,w是顶点，v为弧尾，w为弧头 无向图：E(G)是边的有限集合，边是顶点的无序对，记为（v,w）或（w,v)，并且（v,w)=(w,v)

6 E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
例 2 4 5 1 3 6 G1 图G1中：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 4 G2 6 图G2中：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)}

7 子图——如果图G(V,E)和图G’(V’,E’),满足：
V’V E’E 则称G’为G的子图 3 5 6 例 2 4 1 G G2

8 边/弧数目 用n 表示图中顶点数目，用e 表示图中边或弧的数目 有向图：0 ≤ e ≤ n(n-1) 有向完全图 e = n(n-1)
稀疏图： e < nlogn 稠密图 例 2 1 3 有向完全图 完全图

9 权、网 权：有些图对应每条边有一相应的数值。这个数值叫该边的权。 网：这种带权的图叫网。 注：不同网络的权有不同的意义：电网的权可以是阻抗，运输网络中的权可以是路程长度，运费等。

10 路径与连通性 邻接点：对无向图G=（V，E），若有（V1，V2）属于E则称V1和V2互为邻接点。
相关边：两个相邻接的点连成的边叫做这两个结点的相关边。 度：与每个顶点相连的边的数叫该点的度。记为TD(V) 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目，记为ID(V) 出度：以该顶点为尾的弧的数目，记为OD(V) 例 1 5 7 3 2 4 G2 6 顶点5的度：3 顶点2的度：4 例 2 4 5 1 3 6 G1 顶点2入度：1 出度：3 顶点4入度：1 出度：0

11 路径：路径是顶点的序列V={Vi0,Vi1,……Vin}，满足(Vij-1,Vij)E 或 <Vij-1,Vij>E(1<jn)
路径长度：指路径上边或弧的数目 回路：第一个顶点和最后一个顶点相同的路径叫~ 简单路径：序列中顶点不重复出现的路径叫~ 简单回路：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路叫~

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

13 连通：从顶点V到顶点W有一条路径，则说V和W是连通的
连通图：图中任意两个顶点都是连通的叫~ 连通分量：非连通图的每一个连通部分叫~（极大连通子图） 强连通图：有向图中，如果对每一对Vi,VjV, ViVj,从Vi到Vj 和从Vj到 Vi都存在路径，则称G是~ 强连通分量：有向图中的极大强连通子图 生成树：极小连通子图，一个连通的生成树，它含有图中全部顶点，但只有足以构成树的N-1条边（N顶点个数） 极大、极小是就边数的多少而言的 连通图 例 2 4 5 1 3 6 3 5 6 例 强连通图 例 2 4 5 1 3 6 非强连通图 强连通分量

14 G3 D E I G H K A C B F L J M A C B F L J M A C B F L J M A C B F L J M 连通分量 D E 生成树 I G H K I G H K I G H K 思考：若无向图中有21条边，则： 1) 保持该图不连通至少应具有多少个顶点？ 2) 保持该图连通至少有多少个顶点，至多有多少个顶点？ 1) m个顶点形成完全图，另一个顶点与这m个顶点不连通 ½ m(m-1)=21  m=7  n=m+1=8 2) 至少有 7 个顶点(完全图)，至多有22个顶点(生成树)

15 6.2 图的存储结构 图的存储表示分析 特点：顶点之间的关系是多对多(m : n)
也不适合用多重链表表示。 存储结构：数组表示法（邻接矩阵）、邻接表、多重邻接表、十字链表

16 多重链表 V1 V2 ^ ^ V4 ^ V3 ^ 例 G1 2 4 1 3 例 1 5 3 2 4 G2 ^ V1 V2 V4 ^ V5 ^

17 6.2 图的存储结构-邻接矩阵 数组表示法（邻接矩阵）：表示顶点间相联关系的矩阵
定义：设G=(V,E)是有n1个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵 网的邻接矩阵定义： 其它

18 邻接矩阵     例 G1 2 4 1 3      例 1 5 3 2 4 G2      例 1 4 5 2
7 8 6

19 6.2 图的存储结构-邻接矩阵 无向图/网—对称矩阵 有向图/网—未必是对称矩阵 G3 G2 G1 V1 V2 V1 V2 V1 V2 V3
无向图/网—对称矩阵 有向图/网—未必是对称矩阵 G3 G2 G1 V1 5 V2 V1 V2 V1 V2 4 3 8 7 V3 V6 9 V3 6 1 V3 V4 5 V4 V5 V5 V4 5 V1的度： 第1行或列中值为1的元素个数 V1的出度 V1的入度 V1的出度 ∞ 5 ∞ 7 ∞ ∞ ∞ ∞ 4 ∞ ∞ ∞ 8 ∞ ∞ ∞ ∞ 9 ∞ ∞ 5 ∞ ∞ 6 ∞ ∞ ∞ 5 ∞ ∞ 3 ∞ ∞ ∞ 1 ∞

20 6.2 图的存储结构-邻接矩阵 特点： 无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图需存储空间为n(n+1)/2
无向图中顶点Vi的度TD(Vi)是邻接矩阵A中第i行元素之和 有向图中， 顶点Vi的出度是A中第i行元素之和 顶点Vi的入度是A中第i列元素之和

21 邻接矩阵法优点： 缺点： 容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。仅耗费 O(1) 时间。
n个顶点需要n*n个单元存储边(弧);空间效率为O(n2)。 对稀疏图而言尤其浪费空间。

22 建立无向网络邻接矩阵算法 G vexs[4] arcs[4][4] #define INFINITY 32767
typedef char vertype; typedef struct {vextype vexs[n]； int arcs[n][n]； int vexnum,arcnum; }AMGraph； A B C D vexs[4] ∞ arcs[4][4] G A C B D 无向网络 5 7 1 9 5 7 9 5 7 1 9 1

23 建立无向网络邻接矩阵算法 #define INFINITY 32767 typedef char vertype;
typedef struct {vextype vexs[n]； int arcs[n][n]； int vexnum,arcnum; }AMGraph； Status CreateGraph(AMGraph *G ){ int i,j,w; VexType v1, v2; // 输入顶点数、边数 scanf(“%d%d”, & G-> vexnum, G-> arcnum); for(i = 0; i< G-> vexnum; i++) // 读入所有的顶点 scanf(“%c”, & (*G). vexs[i]); for(i = 0; i < G-> vexnum; i++) //初始化邻接矩阵 for(j = 0; j< G-> vexnum; j++) G-> arcs[i][j] = INFINITY; for(i=0; i< G-> arcnum; i++) { // 输入所有的边 // 输入一条边依附的两个顶点和边上的权值 scanf(“%c%c%d”, &v1, &v2, &w); // 查询两个顶点在图中存储的位置 i = LocateVex(&G, v1); j = LocateVex(&G, v2); G-> arcs[i][j].adj = w; G-> arcs[j][i] = G-> arcs[i][j]; } return OK; } 23/

24 // 查找某个顶点在图中的存储位置（下标），找不到返回-1 int LocateVex(AMGraph *G, VexType vert){
int i; for(i=0; i< G-> vexnum; i++) if(G->vexs[i] = = vert) return i; return -1; } 24/

25 6.2 图的存储结构-邻接表 实现：为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点Vi的边（有向图中指以Vi为尾的弧）
表结点： typedef struct node { int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; //链域，指示下一条边或弧 }JD; 头结点： typedef struct tnode { int vexdata; //存放顶点信息 struct node *firstarc; //指示第一个邻接点 }TD; TD ga[M]; adjvex next vexdata firstarc

26 1 2 3 a c d b vexdata firstarc ^ adjvex next 例 G1 b d a c 1 2 3 a c d b vexdata firstarc ^ adjvex next 4 e 例 a e c b d G2

27 从无向图的邻接表可以得到如下结论： 无向图中顶点Vi的度为第i个单链表中的结点数 所有链表中结点数目的一半为图中边数；
占用的存储单元数目为n+2e 。 G2 V1 V2 V3 V4 V1的度 V5 V1 V2 V3 V4 V5 0 1 2 3 4 1 ^ 0 ^

28 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表
从有向图的邻接表可以得到如下结论： 顶点Vi的出度为第i个单链表中的结点个数 顶点Vi的入度为整个单链表中邻接点域值是i的结点个数 所有链表中结点数目为图中弧数； 占用的存储单元数目为n+e 。 逆邻接表：有向图中对每个结点建立以Vi为头的弧的单链表 V1的出度 V1的入度 G1 V1 V2 V1 V2 V3 V4 0 1 2 3 3 ^ 0 ^ 2 ^ 逆邻接表—入边表 V1 V2 ^ V3 V4 0 1 2 3 1 ^ 0 ^ 3 ^ 邻接表—出边表 V3 V4

29 邻接表的优点： 邻接表的缺点： 空间效率高；容易寻找顶点的邻接点；
判断任意两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。

30 图的邻接表存储表示： #define MAX_VERTEX_NUM 20 struct ArcNode{
int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 网的权值指针 } ArcNode; // 表结点 typedef struct{ VertexType data; // 顶点信息 ArcNode *firstarc; // 第一个表结点的地址 } VNode, AdjList[MAX_VERTEX_NUM]; // 头结点 typedef struct { AdjList vertices; int vexnum,arcnum; // 图的当前顶点数和弧数 }ALGraph; 30/

31 采用邻接表表示法创建无向图 算法思想： （1）依次读入图的各顶点数据并将其存入到头结点数组中，并将表头结点数组的链域均置“空”;
（2）逐个输入表示边的顶点序号（i，j）。 对于每一个有效的顶点对（i，j） ，动态生成两个结点，它们的顶点域 分别为j，i，并分别插入到第i个和第j个链表（为简便起见，插入的位置为第一个结点之前）中。 31/

32 6.2 图的存储结构-十字链表（有向图） 有向图:邻接表-出边表：求入度不方便; 逆邻接表-入边表 十字链表： 弧结点数==弧数 弧结点：
typedef struct arcnode { int tailvex, headvex; //弧尾、弧头在表头数组中位置 struct arcnode *hlink；//指向弧头相同的下一条弧 struct arcnode *tlink; //指向弧尾相同的下一条弧 }AD; tailvex headvex hlink tlink 顶点结点： typedef struct dnode { int data; //存与顶点有关信息 struct arcnode *firstin；//指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; //指向以该顶点为弧尾的第一个弧结点 }DD; DD g[M]; data firstin firstout

33 例 b d a c a b c d 1 2 3 0 2 0 1 2 3 2 0 3 2 3 1 3 0 ^ ^ ^ ^ ^ ^ ^ ^

34 6.2 图的存储结构-邻接多重表（无向图） 无向图：邻接表的每条边对应2个表结点 多重邻接表： 边结点数==边数 边结点：
typedef struct node { int mark; //标志域 int ivex, jvex; //该边依附的两个顶点在表头数组中位置 struct node *ilink, *jlink; //分别指向依附于ivex和jvex的下一条边 }JD; mark ivex ilink jvex jlink 顶点结点： typedef struct dnode { int data; //存与顶点有关的信息 struct node *firstedge; //指向第一条依附于该顶点的边 }DD; DD ga[M]; //ga[0]不用 data firstedge

35 例 a e c b d 1 2 3 a c d b 4 e ^ ^ ^ ^ ^

36 小结 图的定义和术语 图(Graph)、有向图、无向图、子图、有向完全图 、完全图、稀疏图、稠密图、权、网、邻接点、相关边、度、路径、路径长度、回路、简单路径、简单回路、连通、连通图、连通分量、强连通图、强连通分量、生成树 图的存储方法 邻接矩阵、邻接表、十字链表 、邻接多重表 重点：图的邻接矩阵和邻接表的存储结构，建立无向网络邻接矩阵和邻接表的算法。

37 作业 1.讨论邻接表与邻接矩阵的异同之处 。 2.编写程序实现有向图的邻接矩阵和邻接表算法。