第7章 图.

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

1 第7章 图

2 第7章 图 7．1 图的基本概念及术语 7．2 图的存储结构 7．3 图的遍历 7．4 图的应用 7．5 应用举例及分析 习题

3 7．1 图的基本概念及术语 一、基本概念： 图：图G（Graph）由两个集合构成，记作G=（V，E），V是顶点的有穷非空集合；E是用顶点对表示的边（Edge）的有穷集合。 顶点：图中的数据元素通常称为顶点（vertex）。 无向图：若G中表示边的顶点对是无序的，则称为无向图。 通常用（Vi，Vj）表示顶点Vi和Vj间相连的边，(Vi，Vj)与（Vj，Vi）同边。 有向图：若图中表示边的顶点是有序的，则称G为有向图。 弧：有向边通常称为弧（Arc），用<Vi，Vj>表示从顶点Vi到顶点Vj的一条弧，并称Vi为弧尾（始点），Vj是弧头（终点）。在有向图中，<Vi，Vj><Vj，Vi>表示两条不同的弧。

4 n个顶点的有向图中，边e的取值范围为0～n(n-1)条， n个顶点的无向图中，边e的取值范围为0～n(n-1)/2条

5 二．图的基本术语： 1、邻接点，相关边 对于无向图G=（V，E），若边（Vi，Vj）∈E，则称Vi和Vj互为邻接点（Adjacetnt），而边（Vi，Vj）则是与顶点Vi和Vj相关联的边。 对于有向图G=（V，E），若弧<Vi，Vj>∈A，则称顶点Vi邻接到顶点Vj，顶点Vj邻接自顶点Vi，而弧<Vi，Vj>和顶点Vi，Vj相关联。 例如在上页的图中：G1中V3邻接到V1，V1邻接自V3。与V3相关联的弧有：<V2，V3>、<V3，V1>、<V3，V4>。G2中，与V2相关联的边有：<V1，V2> <V2，V3>。

6 2、 完全图 在无向图中，若每对顶点之间都连有一条边，则称该图为无向完全图。n个顶点的图具有n(n-1)条弧的有向图称为有向完全图。 3、 子图 对于图G=（V，E），G′=（V′，E′），若有V′∈V，E′∈E，则称图G′是G的子图。

7 4、 顶点的度（degree） 顶点的度是图中和Vi相关联的边的数目，记为TD（Vi）。 在有向图中，要区别顶点的入度与出度。 入度(indegree)指以Vi为头的弧的数目,记为ID(Vi); 出度(outdegree)指以Vi为尾的弧的数目,记为OD(Vi)； 故顶点的度TD（Vi）=ID（Vi）+OD（Vi） 有n个顶点，e条边的弧的图中，有2e=∑TD(Vi)

8 5、 路径，回路 无向图G=（V，E）中，路径是从顶点V到顶点V′间的一个顶点序列（V=Vi0，Vi1，Vi2，Vi3，……，Vim=V′），其中，（Vij-1，Vij）∈E（1≤j≤m）。 若是有向图，路径也是有向的。 路径的起点和终点相同（即V=V），则称此路径为回路或环（cycle） 简单路径：序列中顶点不重复出现的路径。 ★ 路径上边或弧的数目称为路径长度

9 6、 连通，强连通 若从顶点Vi到Vj(i≠j)有路径，则称Vi和Vj是连通的。
在有向图中，若任意两个顶点Vi和Vj都连通，即从Vi到Vj和Vj到Vi都有路径，则称该有向图为强连通图。有向图中的极大连通子图称为该有向图的强连通分量。

10 7、 权、网 在一个图的每条边或弧上，标上具有某种含义的数值，这种与图的边相关的数值称为权（weight），这种边或弧上带权的图称为网（network）。

11 7．2    图的存储结构 邻接矩阵表示法： 1、定义：设G=（V，E）是N个顶点的图（顶点序号依次为0，1，2，3，……n-1）。G的邻接矩阵是表示图中顶点之间相邻关系的n阶方阵。适用于有向图和无向图。

12 2、n阶方阵A具有如下性质： 1 若（Vi，Vj）或（Vi，Vj）∈E A[i][j]= 0 其他情况 例如，前述G1、G2的邻接矩阵如下：
0 其他情况 例如，前述G1、G2的邻接矩阵如下： 列出图示的邻接矩阵 G1.arc= G2.arc=

13 3、邻接矩阵表示法的性质： 对于无向图： 对于有向图： 1．邻接矩阵一定是对称的
2．第i行（或第i列）非0元素个数正好是第i个顶点的度TD（Vi） 对于有向图： 1．邻接矩阵不一定对称 2．第i行非0元素的个数是顶点i的出度OD（Vi），第i列非0元素的个数是顶点i的入度ID（Vi） 3. 结构说明如下

14 #define VEXTYPE int #define ADJTYPE int #define MAXLEN 40 type struct {LOXTYPE vex[MAXLEN] ; //顶点信息 ADJTYPE arc[MAXLEN][MAXLEN] //邻接矩阵相邻关系 int vexnum , arcnum ; //顶点数，边数 int kind ; } MGRAPH [matrix]

15 7.2.2 邻接链表表示法 邻接链表是图的一种链式存储结构。适用于无向图，也适于有向图。在邻接链表中，对图中的每个顶点建立一个单链表。单链表中的结点称为表结点。单链表有一个表头结点。 表头结点的结构为: Vertex Link ★其中，Vertex域存放图中顶点Vi的信息，Link域为指针，指向对应的单链表中的结点。邻接链表将所有表头结点组成一个二维数组。

16 表结点的结构为： Adjvex Next ★其中，Adjvex域存放与顶点Vi相邻接的顶点在二维数组中的序号， Next域为指针，指向与顶点Vi相邻接的下一个顶点的表结点。

17 无向图G2的邻接链表示意图如下： VER Link adj next V1 1 2 3 ^ V2 V3 V4

18 有向图G1的邻接链表示意图如下： VER Link adj next V1 1 3 ^ V2 2 V3 V4

19 图的邻接链表的结构说明： #define VEXTYPE int #define MAXLEN 40
typedef struct node3 { int adjvex; struct node3 *next; }EDGENODE; typedef struct { VEXTYPE vertex; EDGENODE *link; }VEXNODE; {VEXNODE adjlist[MAXLEN]; int vexnum,arcnum; int kind; }ADJGRAPH;

20 7．3 图 的 遍 历 图的遍历：从图中某顶点出发对图中每个顶点访问一次，而且只访问一次，这一过程称为图的遍历。
7．3 图 的 遍 历 图的遍历：从图中某顶点出发对图中每个顶点访问一次，而且只访问一次，这一过程称为图的遍历。 图的遍历方法有：深度优先搜索遍历和广度优先搜索遍历。

21 7.3.1 深度优先搜索遍历 算法描述：从图中某个顶点V出发，首先访问此顶点，然后任选 一个V的未被访问的邻接点W出发，继续进行深度优先搜索，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选一个图中未曾访问的顶点作始点，重复上面的过程，直至图中所有的顶点都被访问。

22 无向连通图的深度优先搜索过程 V 1 2 3 4 5 V8 6 7 ① ⑤ ⑥ ② ⑦ ③ ④

23 7.3.2 广度优先搜索遍历 算法描述：从图中某个顶点V出发，访问此顶点，然后依次V的各个未被访问的邻接点，再分别从这些邻接点出发，依次访问它们的各个未被访问的的邻接点，邻接点出发的次序按“先被访问的先出发”的原则，直至图中前面已被访问的顶点的邻接点都访问到；若此时图中尚有顶点未被访问，则另选一个图中未曾访问的顶点作始点，重复上面的过程，直至图中所有的顶点都被访问。

24 无向连通图的广度优先搜索过程 V 1 2 3 4 5 V8 6 7 ① ② ③ ④ ⑤ ⑥ ⑦

25 7．4 图 的 应 用 7.4.1 生成树与最小生成树 生成树:由N-1条边将G中N个顶点连接成G的极小连通子图，该极小连通子图就是G 的一棵生成树。 最小生成树问题：一棵生成树的代价定义为生成树上各边权值之和。要选择一棵代价最小的生成树的过程称为最小生成树问题。最小生成树的构造算法有多种，最著名的是 Prim（普里姆）算法。

26 求连通网的最小生成树过程示意： 1 2 5 3 6 4 1 3 2 5 4 2 5 3 6 4

27 7.4.2 拓扑排序 一、概念 无环图：一个无环的有向图称作有向无环图，简称DAG图。
7.4.2 拓扑排序 一、概念 无环图：一个无环的有向图称作有向无环图，简称DAG图。 AOV网：用顶点表示活动，用弧表示活动之间的优先关系的有向图称为AOV网。 在AOV网中，不应该出现有向环路，因为环路表示顶点之间的先后关系进入了死循环。通过对有向图进行拓扑排序来检测图中是否存在环路。

28 拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中顶点的序列必须满足下列条件方可称为有向图的拓扑序列：若在有向图G中，从顶点Vi到Vj有一条路径，则在序列中，顶点Vi排在顶点Vj之前。若从顶点Vi到顶点Vj没有路径，则在序列中给这两个顶点安排一个先后次序。若有向图G所以的顶点都在拓扑序列之中，则AOV网中必定不存在环。 拓扑排序：实现一个有向图的拓扑序列的过程。

29 二、拓扑排序的算法描述 1）在有向图中选择一个入度为0的顶点，输出该顶点； 2）从图中删除该顶点和所有以它为顶点的弧； 3）重复执行1）2），直到找不到入度为0的顶点时，拓扑排序完成。

30 7.4.3 最短路径 以带权有向图为数据结构，求最短路径的问题常用于现实生活中的求几个城市之间的交通网络等问题。
迪杰斯特拉算法求最短路径的基本思想： 设有向网络G=(V,E),把网络中所以顶点分成两组，第一组S包括已确定最短路径的顶点，初始时只含有源点；第二组V-S包括尚未确定最短路径的顶点，初始时含有图中除源点外的所有其他顶点。按路径长度递增的顺序计算源点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至S=V。

31 7.5 应用举例及分析 C 2 1 6 3 4 5 e1 e5 e7 e4 e3 e2 e6 例7.1拓扑排序实用程序。 对应该有向图，用邻接链表结构存储此图。程序首先调用建立有向图邻接链表的算法，建立有向图的邻接链表，在此邻接链表结构上，实现对有向图的拓扑排序并输出结果。

32 #include “stdio.h” #include”alloc.h” #define MAXLEN //有向图顶点最大数目 #define VEXTYPE int //有向图顶点类型 typedef struct gnode //每条弧对应一个结点 { int adjvex; struct gnode * next; }EDGENODE; typedef struct { int id; //顶点的入度 VEXTYPE vextex; //顶点的信息 EDGENODE * ;link; //每个顶点对应一单链表 }VEXNODE;

33 typedef struct {VEXNODE adjlist[MAXLEN]; //邻接链表 int vexnum,arcnum; //有向图的顶点数目、弧数目 int kind; //有向图的 kind = 1 }ADJGRAPH; ADJGRAPH creat_adjgraph() { EDGENODE * p; Int I,s,d;

34 ADJGRAPH adjg; adjg,kind = 1; printf(“请输入顶点数和边数：”)； scanf(“%d %d”,&s,&d); adjg.vexnum = s; adjg.arcnum = d; for(i = 0; j < adjg.vexnum; i++) //邻接链表顶点初始化 {printf(“第 %d个顶点信息：”，i +1); getchar();

35 scanf(“%d”,&adjg.adjlist[i].vextex);
adjg.adjlist[i].link = NULL; adjg.adjlist[i].id = 0;} for(i=0; i< adjg.arcnum; i++) //每条弧的信息初始化 {printf(“第 %d条边的起始顶点编号和终止顶点编号:\n”,i + 1); scanf(“%d,%d”,&s,&d); while(s < 1||s > adjg.vexnum|| d < 1 || d > adjg.vexnum) {printf(“ 编号超出范围，重新输入：”)； scanf(“%d,%d”,&s,&d)}

36 s- -; d- -; p = malloc(sizeof(EDGENODE)); //每条弧对应生成一个结点 p -> adjvex = d; p -> next = adjg.adjlist[s].link; //结点插入对应的链表中 adjg.adjlist[s].link = p; adjg.adjlist[d].id++; //弧对应的终端顶点入度加1 } return adjg;

37 void topsort(ADJGRAPH ag)
//拓扑排序过程 { int i, j, k, m, n, top; EDGENODE * p; n = ag.vexnum; top = -1 for(i = 0; i < n; i++) //将入度为0的顶点压入一个链栈，top指向栈顶结点 If(ag.adjlist[i].id = = 0) //这是一个利用id为0的域链接起来的寄生栈 {ag.adjlist[i].id = top; top = i;}

38 m = 0; while(top 1 = -1) //当栈不空时，进行拓扑排序 {j = top; printf(“%3c”, ag.adjlist[j].vertex); //输出栈顶元素并删除栈顶元素 m++; p = ag.adjlist[j].link; while(p ! = NULL) { k = p ->adjvex; ag.adjlist[k].id - -; //删除相关的弧 if(ag.adjlist[k].id = 0) //出现新的入度为0的顶点，将其入栈 {ag.adjlist[k].id = top; top = k;} p = p ->next;} }

39 if(m < n) printf(“\n网中有环!\n”); //拓扑排序过程中输出的顶点数<有向图中的顶点数 } main() { ADJGRAPH ag; Ag = creat_adjgraph(); topsort(ag);

40 例7.2求最短路径实用程序。 对应右边的有向网，用邻接矩阵结构存储此图。程序首先建立有向图的邻接矩阵，在此邻接矩阵结构上，计算图中从顶点V1出发到其他各顶点的最短路径，并输出结果。 1 2 5 3 4 10 100 30 50 60 20

41 #include “datastru.h” #include “stdio.h” #include “alloc.h” #define MAX 10000 MGRAPH create_mgraph() { int i, j, k, h; char b, t; MGRAPH mg; mg. kind = 3 printf(“请输入顶点数和边数：”)； scanf(“%d,%d”,&i, &j); mg.vexnum = i; mg.arcnum = j; for( i = 0 ;i < mg . vexnum ; i++) { getchar () ; printf ( “第 % d 个顶点信息：”, i + 1); scanf ( “ % c”, & mg . vexs [i]); } for ( i = 0 ; i < mg .vexnum ; i ++) for ( j = 0 ; j < mg . vexnum ; j ++) mg . arcs [i][j] = MAX ;

42 for ( k = 1 ; k < = mg . arcnum ; k ++)
{ printf ( “ \ n 第 % d条边的起始顶点编号和终止顶点编号：” , k); scanf (“ %d , %d”, &i , & j); while ( i <1 | | i > mg . vexnum | | j < 1 | | j > mg . vexnum) {printf ( “编号超出范围，重新输入：\ n \ t”); scanf ( “ %d ,%d” ,& i , &j)} printf (“此边的权值：”); scanf (“%d” ,& h); mg . arcs [i - 1] [j - 1] = h; return mg ; } main ( ) { MGRAPH mg ; Int cost [MAXLEN] [MAXLEN] ; Int path [MAXLEN] , s [MAXLEN] ; Int dist [MAXLEN] ; Int i , j , n , v0 , min , u ; Mg = create_mgraph () ; //建立有向图的邻接矩阵结构

43 Printf (“请输入起始顶点的编号：”) ; //有向图中顶点的编号从 1 编起
Scanf (“%d”, & v0); Vo - - ; n = mg . vexnum ; for ( i = 0 ; i < n ; i ++) //cost 矩阵初始化 {for( j = 0 ; j < n ; j ++) cost [i] [j] = mg .arcs [i][j]; cost [i][j] = 0;} for (i = 0 ; i < n ; i ++) {dist [i] = cost [v0][i]; if (dist[i] < MAX & & dist [i] >0) //dist数组初始化 path [i] =v0 ;} // path数组初始化 s[i] = 0; //s数组初始化 s [v0] =1 ;}

44 for( i= 0 ; i < n ; i ++) // 按最短路径递增算法计算
{min = MAX ; u= v0; for ( j=0 ; j< n ; j++) if (s[j] = = 0 && dist [j]< min) {min = dist [j]; u=j;} s[u] = 1; //u顶点是求得最短路径的顶点编号 for (j = 0 ; j< n ; j++) if (s[j]= = 0 && dist[u] +cost [u][j]<dist[j]) // 调整dist {dist[j] = dist[u] + cost[u][j]; path[j] = u;} //path记录了路径经过的顶点 }

45 for(i = 0;i<n ; i++) //打印结果
if (s[i] = = 1) {u=i; while(u! = v0) {printf(“%d < -”,u+1); u= path[u];} printf(“%d”, u+1); printf(“d=%d\n”, dist[i]); //有路径 } else printf(“%d < - %d d=MAX \n”,i +1, v0+1); //无路径

46 习题 P , 7.3, 7.4, 7.5 , 7.12