第6章 图 北京师范大学 教育技术学院 杨开城.

Presentation on theme: "第6章 图 北京师范大学 教育技术学院 杨开城."— Presentation transcript:

1 第6章 图 北京师范大学 教育技术学院 杨开城

2 一、基本概念和术语 有向图 无向图 网 子图 路径 回路 连通图 连通分量 强连通图 生成树 顶点 边 弧 弧头 弧尾 出弧 入弧 邻接
有向图 无向图 网 子图 路径 回路 连通图 连通分量 强连通图 生成树 顶点 边 弧 弧头 弧尾 出弧 入弧 邻接 度 入度 出度

3 二、图的存储结构——邻接矩阵(1) typedef struct vexinfor { VEXINFO vinfo;/*顶点的其他信息*/
char vexchar; /*顶点的名称*/ }VEX[N]; typedef struct { VEX vexes; /*存放顶点的数组*/ int arcs[N][N]; /*存放关系的二维数组*/ int vexnum,arcnum; /*vexnum是顶点个数，arcnum是边或弧的个数*/ }MGRAPH;

4 二、图的存储结构——邻接矩阵(2) 邻接矩阵的生成算法 #define MAX 32767
void inputMGraph(MGRAPH *g) { /*从一个文件中读取图的数据，建立一个邻接矩阵g*/ int i,j,vexnum=0,weight; FILE *fp; char ch1,ch2; char str[80]; for(i=0;i<N;i++) for(j=0;j<N;j++) g->arcs[i][j]=MAX;/*初始化邻接矩阵，所有单元都是∞*/ vexnum=0; /*顶点计数为0*/ g->vexnum=0; g->arcnum=0; /*邻接矩阵的顶点数和弧数初始化为0*/ fp=fopen("gdata.txt","rt");/*打开输入数据文件gdata.txt*/ if(fp==NULL) /*打开文件失败*/ { printf("can't open gdata.txt\n"); return; }

5 二、图的存储结构——邻接矩阵(3) while(1) /*读取数据的循环，一次读入一行文本，即读入一个弧*/
{ str[0]=0; fgets(str,79,fp);/*读入一行文本*/ i=strlen(str); if(str[i-1]=='\n')str[i-1]=0; /*去掉末尾的换行符*/ if(str[0]==0)break;/*空行，意味着数据输入结束，跳出循环*/ sscanf(str,"%c,%c,%d",&ch1,&ch2,&weight);/*获取顶点字符和权值*/ for(i=0;i<vexnum;i++) /*检查数组vexes中是否存在字符ch1*/ if(g->vexes[i].vexchar==ch1)break; if(i==vexnum) /*说明vexes中没有ch1，需要将ch1增加到数组中*/ { if(vexnum==N)/*顶点数饱和*/ { printf("too many vexes!\n"); return; } else /*将ch1保存在vexes中，顶点数vexnum增1*/ g->vexes[vexnum++].vexchar=ch1; }

6 二、图的存储结构——邻接矩阵(4) for(j=0;j<vexnum;j++)/*检查数组vexes中是否存在字符ch2*/
if(g->vexes[j].vexchar==ch2)break; if(j==vexnum) /*说明vexes中没有ch2，需要将ch2增加到数组中*/ { if(vexnum==N) /*顶点数饱和*/ { printf("too many vexes!\n"); return; } else /*将ch2保存在vexes中，顶点数vexnum增1*/ g->vexes[vexnum++].vexchar=ch2; } /*至此，顶点处理完毕，i,j分别是ch1,ch2顶点的下标*/ g->arcs[i][j]=weight; /*邻接矩阵相应单元设置为权值weight*/ g->arcnum++; /*弧的个数增1*/ fclose(fp);/*关闭文件*/ g->vexnum=vexnum;/*设置邻接矩阵的顶点数*/

7 二、图的存储结构——邻接表(1) typedef struct arcnode /*定义弧或边链表中的结点类型*/
{ int adjvex; /*邻接顶点的下标*/ int weight; /*弧或边的权值*/ struct arcnode *nextarc; /*指向下一个弧或边结点*/ }ARCNODE , *ARCNODEPTR; typedef struct { VEXINFO vinfo;/*顶点的其他信息*/ char vexchar; /*顶点名称*/ ARCNODE firstarc; /*与顶点相连的边或者弧的链表的头结点*/ }ADJLNODE,*ADJLIST; ADJLIST vertices; /*指向存放顶点和边/弧链表头结点的数组*/ int vexnum,arcnum; /*顶点个数，边或弧的个数*/ }ALGRAPH;

8 二、图的存储结构——邻接表(2) 邻接矩阵转换为邻接表的算法
int MGraphToALGraph(MGRAPH *mg,ALGRAPH *alg) { /*将邻接矩阵mg转换为邻接表alg，假定mg中是一个有向网。操作成功返回1，否则返回0*/ int i,j; ARCNODEPTR p; alg->vexnum=mg->vexnum;/*复制顶点数和弧数*/ alg->arcnum=mg->arcnum; /*根据顶点数分配邻接表的vertices数组*/ alg->vertices=(ADJLIST)malloc(alg->vexnum*sizeof(ADJLNODE)); if(alg->vertices==NULL)return 0;/*操作失败*/ for(i=0;i<alg->vexnum;i++) /*复制顶点数据，并为顶点建立出弧链表*/ { alg->vertices[i].vexchar=mg->vexes[i].vexchar;/*复制顶点名称*/ alg->vertices[i].firstarc.nextarc=NULL;/*将出弧链表设为空链表*/

9 二、图的存储结构——邻接表(3) for(j=0;j<mg->vexnum;j++) /*遍历邻接矩阵的第i行，建立出弧链表*/
{ if(mg->arcs[i][j]!=MAX) /*存在弧<Vi,Vj>*/ { p=(ARCNODEPTR)malloc(sizeof(ARCNODE));/*生成弧结点*/ if(p==NULL) /*分配失败，返回0之前，销毁已经生成的邻接表*/ { printf("no enough memory\n"); DestroyALGraph(alg);/*见后面的算法*/ return 0; } /*设置弧的基本信息：邻接顶点和权值*/ p->adjvex=j; p->weight=mg->arcs[i][j]; /*将弧结点插入链表中*/ p->nextarc=alg->vertices[i].firstarc.nextarc; alg->vertices[i].firstarc.nextarc=p; } }/*属于for(j 语句*/ }/*属于for(i 语句*/ return 1; }

10 二、图的存储结构——邻接表(4) 邻接表的销毁算法
void DestroyALGraph(ALGRAPH *alg) /*销毁邻接链表alg*/ { int i; ARCNODEPTR p; for(i=0;i<alg->vexnum;i++) /*遍历所有顶点，销毁该顶点的出弧链表*/ { while(alg->vertices[i].firstarc.nextarc!=NULL) { p=alg->vertices[i].firstarc.nextarc; alg->vertices[i].firstarc.nextarc=p->nextarc; /*摘除一个弧结点*/ free(p);/*释放弧结点*/ } free(alg->vertices);/*释放数组vertices*/ /*将邻接表中的数据设置成安全值*/ alg->vertices=NULL; alg->vexnum=alg->arcnum=0;

11 三、图的遍历——深度优先遍历(1) 基本思想
首先从某个顶点V出发深度优先遍历整个图。这个过程是一个递归过程：即先访问V，然后依次从V的未被访问的邻接顶点出发深度优先遍历剩余的子图，直到所有的与V邻接的顶点都被访问到。 如果此时，仍有顶点未被访问到，就从那些顶点出发继续深度优先遍历剩余子图，直到所有顶点都被访问到为止。

12 三、图的遍历——深度优先遍历(2) 1．邻接矩阵的深度优先遍历
void DfsTraverseMG(MGRAPH *mg,char *str) {/*深度优先遍历邻接矩阵mg存储的带权图,将遍历结果存放在str中，一开始str是空*/ int *visited;/*辅助数组visited的指针*/ int i; visited=(int *)malloc(mg->vexnum*sizeof(int));/*分配辅助数组visited*/ if(visited==NULL)return ; for(i=0;i<mg->vexnum;i++) /*将visited数组单元全部清零*/ visited[i]=0; /*检查图的所有顶点，遇到未被访问过顶点V，则以V为出发点深度优先遍历图*/ for(i=0;i<mg->vexnum;i++) if(visited[i]==0)/*Vi未被访问过*/ DfsMG(mg,str,i,visited);/*以Vi作为出发点，深度优先遍历mg*/ free(visited);/*释放visited数组*/ }

13 三、图的遍历——深度优先遍历(3) void DfsMG(MGRAPH *mg,char *str,int v,int visited[])
{/*以v作为出发点，深度优先遍历带权图的邻接矩阵mg，将结果存放到str中，visited中记录着各顶点的遍历状态。这是个递归算法*/ char tmpstr[8]="A"; int i; visited[v]=1;/*设置出发点的顶点的遍历状态为1*/ /*将出发点顶点的名称续接到str中*/ tmpstr[0]=mg->vexes[v].vexchar; strcat(str,tmpstr); /*检查所有顶点与顶点mg->vexes[v]的邻接关系，如果mg->vexes[i]与该顶点邻接，并且没有被访问过，则以mg->vexes[i]为出发点深度遍历整个图*/ for(i=0;i<mg->vexnum;i++) if(mg->arcs[v][i]!=MAX&&visited[i]==0) DfsMG(mg,str,i,visited); }

14 三、图的遍历——深度优先遍历(4) 深度遍历的结果是：ABCFDE 深度优先遍历的生成树

15 三、图的遍历——深度优先遍历(5) 2．邻接表的深度优先遍历
void DfsTraverseALG(ALGRAPH *alg,char *str) { /*深度优先遍历邻接表alg，遍历结果存放在str中，一开始str是空*/ int *visited; int i; visited=(int *)malloc(alg->vexnum*sizeof(int));/*分配visited数组*/ if(visited==NULL)return ; for(i=0;i<alg->vexnum;i++) /*将数组visited清零*/ visited[i]=0; /*检查图的所有顶点，遇到未被访问过顶点V，则以V为出发点深度优先遍历图*/ for(i=0;i<alg->vexnum;i++) if(visited[i]==0) DfsALG(alg,str,i,visited); free(visited); }

16 三、图的遍历——深度优先遍历(6) void DfsALG(ALGRAPH *alg,char *str,int v,int visited[]) {/*以v为出发点深度优先遍历邻接表alg*/ char tmpstr[8]="A"; ARCNODEPTR p; int j; visited[v]=1; tmpstr[0]=alg->vertices[v].vexchar; strcat(str,tmpstr); /*将出发点顶点的名称续接到str中*/ p=alg->vertices[v].firstarc.nextarc; while(p!=NULL) /*遍历出发点顶点的弧或边的链表*/ { j=p->adjvex; /*找到一个邻接顶点*/ if(visited[j]==0)/*该邻接顶点未被访问*/ DfsALG(alg,str,j,visited); p=p->nextarc; /*跳到下一个弧或边的结点*/ }

17 三、图的遍历——广度优先遍历(1) 基本思想
首先将出发点顶点入队，并做访问标记。接下来就反复执行出队和入队操作：出队一个顶点，将它的那些没有被访问的邻接顶点入队，入队同时做访问标记。这样反复执行直到队空为止。 邻接表的广度优先遍历算法 void BfsALG(ALGRAPH *alg,char *str,int v,int visited[]) {/*从顶点v(下标)出发，广度优先遍历邻接表alg，将遍历结果存放在str中，visited是辅助数组，一开始全部单元的值都是0*/ SQQUEUE qu; int k,j; ARCNODEPTR p; char tmpstr[8]="A"; InitSqqueue(&qu,alg->arcnum);/*初始化队列*/ EnSqqueue(&qu,v);/*将出发的顶点入队，只是下标入队*/ visited[v]=1;/*做访问标记*/

18 三、图的遍历——广度优先遍历(2) while(!IsSqqueueEmpty(qu)) /*只要队不空，就循环*/
{ DeSqqueue(&qu,&k); /*出队一个顶点Vk*/ tmpstr[0]=alg->vertices[k].vexchar; strcat(str,tmpstr);/*将Vk的顶点名称续接到str中*/ p=alg->vertices[k].firstarc.nextarc; while(p!=NULL)/*遍历Vk的边或弧链表*/ { j=p->adjvex; /*找到Vk的邻接顶点Vj*/ if(visited[j]==0) /*如果Vj未被访问，则入队，并做访问标记*/ { EnSqqueue(&qu,j); visited[j]=1; } p=p->nextarc; /*跳到下一个边或弧结点*/ DestroySqqueue(&qu);/*销毁队列*/

19 三、图的遍历——广度优先遍历(3) 从顶点A出发的广度优先遍历的结果是：ABFCED。

20 四、图的关节点问题(1) 关节点：在图的一个连通分量中，删除一个顶点V以及它的所有的边，如果这个连通分量变成了两个或更多的连通分量，那么这个顶点V被称为这个图的关节点。 重连通图：不存在关节点的图被称为重连通图。 连通度：如果在某个连通图中至少删除k个顶点才能破坏它的连通性，那么称这个图的连通度为k。 通过考察连通图的深度优先遍历生成树，就可以发现关节点

21 四、图的关节点问题(2) 发现关节点的规则 内部关节点的确定规则
⑴如果根结点是关节点，它必然至少有2棵子树。很明显，这种情况下，删除根结点，它的子树之间是不连通的。 ⑵如果某个内部结点V是关节点，那么V一定存在一棵子树，这棵子树所有的结点都没有回边指向V的祖先。这种情况下，删除结点V，V的这棵子树与其他子树之间不连通。 ⑶不存在其他关节点。 内部关节点的确定规则 用visited[i]代表遍历深度 要增加一个辅助数组low，为每个顶点设定一个low值，low[i]的含义是： 顶点 A B D C E G F H I J visited[i] 1 2 3 4 5 6 7 8 9 10 low[i] 求得low[i]值的顺序

22 四、图的关节点问题(3) 求关节点算法的基本思想
⑴从某个顶点Vr出发，深度优先遍历图G，记下每个顶点的遍历深度值，存放在visited数组中。 ⑵深度遍历是一个递归过程，当递归遍历某个顶点Vk时，设定Vk的low[k]值为它的递归深度visited[k]，接下来要递归遍历Vk所有的邻接顶点。设Vj是Vk的一个邻接顶点， ①如果Vj没有被访问，则递归遍历Vj，返回后有两项操作： Ⅰ.如果发现low[j]≥visited[k]，则判定Vk是关节点； Ⅱ.检查low[j]，如果low[j]<low[k]，则将low[k]设成low[j]，即取最小值。 ②如果Vj已被访问过，那么Vj是Vk的祖先，它们之间存在回边。这时检查visited[j]的值，如果visited[j]<low[k]，则将low[k]设成visited[j]，即取最小值。 ⑶一次调用深度优先遍历返回到Vr后，仍发现Vr有邻接顶点未被访问，则可以判定Vr是关节点，并继续递归遍历，寻找其他内部关节点。 设定一个mark数组,一开始mark数组的所有单元都是0，如果发现Vi是关节点，就将mark[i]的值设为1。

23 四、图的关节点问题(4) 求关节点的算法 int mark[N];/*N是顶点个数的最大值*/
void ArticulationALG(ALGRAPH *alg) {/*深度优先遍历无向连通图的邻接表，输出全部关节点*/ int *visited,*low; int n,k,count; int i,x,y; ARCNODEPTR p; n=alg->vexnum;/*获得图的顶点数*/ visited=(int*)malloc(n*sizeof(int));/*分配visited数组*/ low=(int *)malloc(n*sizeof(int));/*分配low数组*/ if(visited==NULL||low==NULL)return ; for(i=0;i<n;i++) mark[i]=0; /*将关节点标志清零*/ k=0;/*k是根顶点下标，可以是任意有效值*/

24 四、图的关节点问题(5) count=1;/*遍历计数器*/
for(i=0;i<n;i++)/*初始化visited数组，根顶点的遍历深度是1*/ if(i==k)visited[i]=1; else visited[i]=0; p=alg->vertices[k].firstarc.nextarc;/*p指向根顶点的第一条边*/ /*下面从根顶点的第一个邻接顶点出发，深度优先遍历这个图，寻找关节点*/ ArticulDfsALG(alg,p->adjvex,k,visited,low,&count); p=p->nextarc;/*p指向根顶点的下一条边*/ while(p!=NULL) /*遍历根顶点的边链表，检查还有无顶点没有被访问到*/ { if(visited[p->adjvex]==0) /*还有邻接顶点没有被访问，根存在至少2棵子树*/ { mark[k]=1;/*根顶点是关节点*/ /*继续从其他邻接顶点出发，深度优先遍历这个图，寻找关节点*/ ArticulDfsALG(alg,p->adjvex,k,visited,low,&count); } p=p->nextarc;/*跳到根顶点的下一条边*/ } free(visited);free(low); }

25 四、图的关节点问题(6) void ArticulDfsALG(ALGRAPH *alg,int k,int parent,int visited[],int low[],int *count) {/*深度优先遍历无向连通图G的邻接表，输出关节点。出发点是Vk，parent是顶点Vk在生成树中的双亲顶点下标，visited数组、low数组已经被分配完毕，count是遍历计数器。读者也可以将visited,low和count按照全局变量处理，而不放在函数参数中*/ ARCNODEPTR p; int j,x,y; (*count)++;/*计数器增1*/ visited[k]=*count;/*设置Vk的遍历深度，同时也是访问标记*/ low[k]=visited[k];/*将遍历深度值暂时作为Vk的low值*/ p=alg->vertices[k].firstarc.nextarc;

26 四、图的关节点问题(7) while(p!=NULL) {/*遍历Vk的边链表，以Vk的邻接顶点为出发点继续深度优先遍历图*/
j=p->adjvex; if(visited[j]==0)/*Vj是Vk的邻接顶点，并且未被访问*/ { ArticulDfsALG(alg,j,k,visited,low,count);/*继续递归调用*/ /*从Vj递归调用返回时，更新Vk的low值，并且判断Vk是否是关节点*/ if(low[j]<low[k]) /*Vj是Vk的孩子，如果low[j]更小，则更新low[k]*/ low[k]=low[j]; if(low[j]>=visited[k]) mark[k]=1;/* Vk是关节点，设定关节点标志*/ } else if(j!=parent) /*p指向一条Vk的回边*/ if(visited[j]<low[k]) /*如果回边指向的顶点遍历深度更小，更新low[k]值*/ low[k]=visited[j]; p=p->nextarc;/*p指向Vk的下一条边*/

27 五、最小生成树 【问题描述】假设某政府想在N个城市之间修建公路，要保证每个城市之间都是连通的。设不同城市之间修建公路的造价不同，由于只需要N-1条公路就可以使得所有城市之间都连通，请问在哪些城市之间修建公路既使得城市之间是连通的，又使得总造价最小？

28 五、最小生成树——Prim算法(1) 【基本思想】
已知一个N个顶点的连通网G=(V,E)，它的生成树是T=(U,TE)，其中U是顶点集合，TE是构成生成树边的集合。一开始T是空树。首先任意选择一个顶点作为T的根。 将树中的顶点集合U看成是一个逻辑顶点，所有树外顶点与树中顶点的边都看成是树外顶点与逻辑顶点的边。在这些边中，选择一条权值最小的，将这条边及其连接的顶点加入到树中，这时逻辑顶点的覆盖范围扩大了一个顶点。 按照相同逻辑重复上述操作，经过N-1次选择后，所建立的生成树就是最小生成树。

29 五、最小生成树——Prim算法(2) typedef struct { int fromvex,endvex;/*边的两个顶点*/
int weight;/*边的权值*/ }EDGE; EDGE *PrimMGraph(MGRAPH *mg) {/*求得邻接矩阵mg的最小生成树，返回值是指向存储生成树边的数组的指针*/ EDGE *pEdge=NULL; EDGE tmpe; int i,j,k,n,t; n=mg->vexnum;/*获得图的顶点数*/ pEdge=(EDGE*)malloc((n-1)*sizeof(EDGE));/*分配边的数组*/ for(i=1;i<n;i++) {/*以第0个顶点为根，即U集只包含一个根，初始化其他顶点与U集的边， 实际上就是将矩阵的一行arcs[0]复制过来*/ pEdge[i-1].fromvex=0;/*边的树内顶点是根*/ pEdge[i-1].endvex=i; /*树外顶点*/ pEdge[i-1].weight=mg->arcs[0][i];/*复制边的权值*/ }

30 五、最小生成树——Prim算法(3) for(i=0;i<n-1;i++)/*开始n-1次选择*/
{ k=i;/*开始一趟按权值升序排列的选择排序*/ for(j=i+1;j<n-1;j++) if(pEdge[j].weight<pEdge[k].weight) k=j; if(k!=i) { tmpe=pEdge[i]; pEdge[i]=pEdge[k]; pEdge[k]=tmpe; } /*至此，pEdeg[i]已经成为权值最小的边*/ j=pEdge[i].endvex;/*顶点Vj将加入U集*/ /*pEdge[i+1..n-2]是下一次待选择的边集合，pEdge[0..i]是最小生成树的边集合*/ for(t=i+1;t<n-1;t++)/*遍历剩下的边，更新它们的权值，Vt是树外顶点*/ if(mg->arcs[pEdge[t].endvex][j]<pEdge[t].weight) {/*(Vj,Vt)的权值更小，将(Vj,Vt)作为Vt与U集的边*/ pEdge[t].fromvex=j;/*更改边的树内顶点*/ pEdge[t].weight=mg->arcs[pEdge[t].endvex][j]; } }//for(i return pEdge;/*返回pEdge，调用者根据需要将生成树输出*/ }

31 五、最小生成树——Kruskal算法(1)
【基本思想】 首先将图的N个顶点自成一个集合。将图中的所有的边按照权值从小到大的顺序排列。 接下来从小到大依次检查这些边，如果边的两个顶点不属于同一个集合，那么就将这条边作为生成树的边，并且将边的顶点集合合并起来。 这样依次选择的N-1条边就构成了最小生成树。

32 五、最小生成树——Kruskal算法(2)
EDGE * KruskalALGraph(ALGRAPH *alg) {/*求得邻接表alg的最小生成树，生成树的边存储在数组中，返回指向这个数组的指针*/ EDGE *pEdge,*pTmpEdge,te; int *setmark; int m,n,i,j,k,s1,s2; ARCNODEPTR p; n=alg->vexnum;/*获得图的顶点数*/ m=alg->arcnum;/*获得图的边数*/ setmark=(int *)malloc(n*sizeof(int));/*分配辅助数组setmark*/ pTmpEdge=(EDGE *)malloc(m*sizeof(EDGE));/*分配容纳m个边的数组*/ pEdge=(EDGE *)malloc((n-1)*sizeof(EDGE));/*分配存放生成树边的数组*/ for(i=0;i<n;i++)setmark[i]=i;/*顶点自成一个集合*/

33 五、最小生成树——Kruskal算法(3)
k=0;/*k是边的计数器*/ for(i=0;i<n;i++) /*遍历所有顶点的边链表，将边信息复制到pEmpEdge数组中*/ { p=alg->vertices[i].firstarc.nextarc; while(p!=NULL) { if(p->adjvex>i) { pTmpEdge[k].fromvex=i; pTmpEdge[k].endvex=p->adjvex; pTmpEdge[k].weight=p->weight; k++; } p=p->nextarc; }//while } if(k!=m) printf("there error in arcs!");/*邻接表中存在错误*/ for(i=0;i<m-1;i++) /*对pTmpEdge数组中的边按照权值进行升序排列*/ { k=i; for(j=i+1;j<m;j++) if(pTmpEdge[j].weight<pTmpEdge[k].weight) k=j; if(k!=i) {te=pTmpEdge[i]; pTmpEdge[i]=pTmpEdge[k];pTmpEdge[k]=te; } }//for

34 五、最小生成树——Kruskal算法(4)
for(i=0;i<m;i++) /*按照从小到大的顺序选择边，并试图将它加入到生成树中*/ { s1=pTmpEdge[i].fromvex; s2=pTmpEdge[i].endvex; /*此时s1,s2是边的顶点，下面将顶点下标转化为集合号*/ s1=setmark[s1]; s2=setmark[s2]; if(s1!=s2) /*边的两个顶点属于不同的集合*/ { pEdge[k]=pTmpEdge[i];/*将这条边复制到pEdge中，加入生成树*/ k++; if(k==n-1)break;/*找到了n-1条边，生成树构建完毕，跳出循环*/ for(j=0;j<n;j++)/*合并集合s1,s2*/ if(setmark[j]==s2) /*将所有属于集合s2的顶点的集合号改为s1*/ setmark[j]=s1; } free(setmark); free(pTmpEdge); return pEdge;/*返回指向生成树边的数组的指针*/

35 六、最短路径问题 【问题描述】某人在N个城市之间旅行，城市之间是连通的，但由于地理环境方面的原因，不同城市之间的交通方式不同，当然花费也不同。问从某城市A出发到达城市B所需要的花费最少的路径是哪一条。 将问题复杂化从某个源点到其他各顶点的最短路径

36 六、最短路径问题——Dijkstra 算法(1)
【思考方式】 从顶点A出发，走哪条路径最短就能到达下一个顶点呢（不管到达的顶点具体是哪一个顶点！）？ 接下来再思考，走哪条路径最短到达下一个顶点呢？ 依此类推，我们就会得到全部的最短路径。

37 六、最短路径问题——Dijkstra 算法(2)
【算法思想】 设定S是已经找到最短路径的顶点的集合，一开始S中只包含一个源点顶点Vv。 设置一个存放N-1条路径的数组Path，存放源点到其他N-1个顶点的路径，即Path[i]表示Vv到Vi的路径。 一开始源点到邻接顶点的路径长度就是相应的出弧或边的权值，而到非邻接顶点的路径长度是∞。 接下来进行N-1次选择，每次都选择最短的一条路径，并且路径的终点不属于S集，然后将终点加入S集。 每当有新顶点Vj加入到S集时，都要尝试更新顶点Vj的不属于S集的邻接顶点的路径。

38 六、最短路径问题——Dijkstra 算法(2)
typedef struct { int *route;/*路径上顶点的序列*/ int totalweight;/*路径长度，即路径上边或弧权值之和*/ }PATH; PATH * ShortestPathALGraph(ALGRAPH *alg,int v) { /*找出邻接表alg中，顶点Vv到其他各个顶点的最短路径，返回存放最短路径的数组的指针*/ PATH *Path; int n,w,i,j,k,m; int *S;/*集合标志*/ ARCNODEPTR p; n=alg->vexnum;/*获得顶点数*/ /*分配容纳n条路径的数组，包含源点到自身的路径*/ Path=(PATH *)malloc(n*sizeof(PATH)); if(Path==NULL)return NULL; S=(int *)malloc(n*sizeof(int));/*顶点的S集合标记*/

39 六、最短路径问题——Dijkstra 算法(3)
/*下面开始初始化Path数组，数组中存放各个顶点到Vv的路径及长度*/ for(i=0;i<n;i++) { Path[i].route=(int *)malloc(n*sizeof(int));/*分配路径静态链数组*/ Path[i].route[v]=i;/*设置初始路径为“Vv,Vi”*/ if(i==v) /*路径是源点到自身的路径，设置路径长度是0，并且设置S集标记为1*/ { Path[i].totalweight=0; S[i]=1; } else /*否则，复制暂时将路径长度设定为∞,设定S集标记为0*/ { Path[i].totalweight=MAX; S[i]=0; } } /*开始遍历源点顶点Vv的边或者出弧，更新Path中的路径长度信息*/ p=alg->vertices[v].firstarc.nextarc; while(p!=NULL) { j=p->adjvex;/*获得Vv的邻接顶点Vj*/ Path[j].totalweight=p->weight;/*设定P(Vv,Vj)为W(Vv,Vj)*/ p=p->nextarc;

40 六、最短路径问题——Dijkstra 算法(4)
/*开始n-1次选择，找到n-1条最短路径*/ for(i=0;i<n-1;i++) { w=MAX; for(j=0;j<n;j++) /*寻找路径长度最小且终点不属于S集的边或弧*/ { if(Path[j].totalweight<w&&S[j]==0) { k=j; w=Path[j].totalweight; } if(w==MAX) break; /*说明其余顶点与源点不连通，最短路径都被找到*/ S[k]=1; /*Path[k]是一条最短路径，把它的终点Vk加入S集*/

41 六、最短路径问题——Dijkstra 算法(5)
p=alg->vertices[k].firstarc.nextarc; while(p!=NULL) /*更新Vk的邻接顶点的最短路径信息，如果这些顶点不属于S集*/ { j=p->adjvex;/*Vj是Vk的邻接顶点*/ if(S[j]==0&&p->weight+Path[k].totalweight<Path[j].totalweight) {/*Vj不属于S集，并且P(Vv,Vk)+W(Vk,Vj)<P(Vv,Vj)， 那么更新Path[j]，选择更短的路径*/ Path[j].totalweight=p->weight+Path[k].totalweight; m=v;/*先将Path[k]的路径route复制到Path[j]上*/ while(m!=k) { Path[j].route[m]=Path[k].route[m]; m=Path[k].route[m]; } Path[j].route[k]=j;/*在Path[k]基础上续接上vj*/ } p=p->nextarc; }//while(p }//for(i free(S); return Path;

42 六、最短路径问题——Dijkstra 算法(6)
void ShowPathALGraph(PATH *path,ALGRAPH *alg) {/*输出邻接表alg的一组最短路径，最短路径存储在数组path中*/ int count=0; int i,v,k; for(i=0;i<alg->vexnum;i++)/*确定源点，源点的路径长度是0*/ if(path[i].totalweight==0)break; v=i;/*Vv是源点*/ for(i=0;i<alg->vexnum;i++) /*输出源点到其他顶点的最短路径*/ { if(i!=v&&path[i].totalweight!=MAX) /*Vv到Vi之间存在最短路径*/ { k=v; while(k!=i) { 输出顶点Vk k=path[i].route[k]; } 输出顶点Vi } }//for(i

43 六、最短路径问题——Floyd 算法(1) 【问题】每对顶点之间的最短路径 【解决方案】 【Floyd算法的基本思想】
针对每个顶点，调用Dijkstra算法 调用Floyd算法 【Floyd算法的基本思想】 依次将V0,V1,…Vn-1尝试插入到每对顶点之间的路径当中，使之更短，最终我们就得到了每对顶点之间的最短路径。这其中的道理主要是： ⑴每次成功的插入，都使得一对连通的顶点之间的路径变得更短。插入操作总体上使得顶点之间的路径趋向最小。 ⑵如果Vk出现在某个最短路径中，那么它的前后顶点一定是它的邻接顶点，并且前后顶点之间已经达到路径最短。在所有的顶点都尝试插入之后，都会达到这个局部最短的效果。这个局部最短的效果也会随着插入操作，扩大为全局最短。

44 六、最短路径问题——Floyd 算法(2) void Floyd(MGRAPH *mg,PATH Path[][N])
int i,j,n,m,k; n=mg->vexnum; for(i=0;i<n;i++) /*将邻接矩阵复制到Path数组中*/ for(j=0;j<n;j++) { if(i==j) Path[i][j].totalweight=0; else Path[i][j].totalweight=mg->arcs[i][j]; Path[i][j].route=(int *)malloc(n*sizeof(int)); if(Path[i][j].route==NULL)return; Path[i][j].route[i]=j;/*设定路径{Vi,Vj}*/ }

45 六、最短路径问题——Floyd 算法(3) for(k=0;k<n;k++)/*将Vk试着插入到Vi和Vj之间*/
for(i=0;i<n;i++) for(j=0;j<n;j++) if(k!=i&&k!=j&&i!=j&& Path[i][k].totalweight<MAX&&Path[k][j].totalweight<MAX&& Path[i][k].totalweight+Path[k][j].totalweight<Path[i][j].totalweight) { Path[i][j].totalweight=Path[i][k].totalweight+Path[k][j].totalweight; /*开始合并路径，将{Vi,...,Vk}和{Vk,...,Vj}合并成{Vi,...,Vj}*/ m=i;/*先复制{Vi,...,Vk}*/ while(m!=k) { Path[i][j].route[m]=Path[i][k].route[m]; m=Path[i][k].route[m]; } while(m!=j) /*续接{Vk,...,Vj}*/ { Path[i][j].route[m]=Path[k][j].route[m]; m=Path[k][j].route[m]; } }//if(k }

46 七、拓扑排序和关键路径——拓扑排序(1) 【问题描述】某项工作中包含有8项任务，它们之间的关系如图6_19所示，任务之间的弧说明了它们的先后次序，比如完成了T1才能做T2、T4和T6，T3和T6做完了才能做T7，等等。请列出一种合理的工作顺序，即先做什么再做什么 图中顶点代表着某个任务或者活动，我们称之为AOV网 拓扑排序是指将一个有向图G中的所有顶点排成一个线性序列，这个线性序列要满足这个要求：如果存在弧<Vi,Vj>，那么在这个线性序列中Vi要排在Vj的前面。 可以通过拓扑排序来判断一个有向图是否存在环。 一个有向无环图的拓扑排序可能存在多个结果。

47 七、拓扑排序和关键路径——拓扑排序(2) 【拓扑排序的基本操作】 【拓扑排序算法的思想】 ①输出所有的没有入弧的顶点；
②删除这些顶点及其出弧，这样会再次出现一些没有入弧的顶点。 【拓扑排序算法的思想】 ①计算所有顶点的入度，将入度是0的顶点全部入队（或入栈）； ②如果队空（或栈空），排序完毕；否则出队(或出栈)一个顶点V，输出顶点V； ③将V的所有邻接顶点的入度减1，如果某邻接顶点的入度变成0，则将其入队(或入栈)。转去执行步骤②。

48 七、拓扑排序和关键路径——拓扑排序(3) void TopoSortQueue(ALGRAPH *alg,char *str)
{ /*求得邻接表alg的拓扑排序序列，存放在str中，一开始str是空*/ int *indegree; int n,i,j,k; char tmpstr[8]="A"; ARCNODEPTR p; SQQUEUE qu; /*辅助队列*/ n=alg->vexnum; /*获得顶点数*/ indegree=(int *)malloc(n*sizeof(int)); /*分配存放顶点入度的数组*/ if(indegree==NULL)return; for(i=0;i<n;i++) indegree[i]=0; /*将所有顶点入度初始化为0*/ for(i=0;i<n;i++) /*遍历所有顶点的出弧链表，计算弧头顶点的入度*/ { p=alg->vertices[i].firstarc.nextarc; while(p!=NULL) { indegree[p->adjvex]++;/*弧头顶点的入度增1*/ p=p->nextarc; } InitSqqueue(&qu,n);/*初始化队列*/

49 七、拓扑排序和关键路径——拓扑排序(4) for(i=0;i<n;i++)/*将入度是0的顶点入队，实际上入队的是顶点下标*/
if(indegree[i]==0)EnSqqueue(&qu,i); while(!IsSqqueueEmpty(qu)) /*只要队列不空，就循环输出顶点*/ { DeSqqueue(&qu,&k);/*出队顶点Vk*/ tmpstr[0]=alg->vertices[k].vexchar; strcat(str,tmpstr);/*将顶点名称续接到str中*/ p=alg->vertices[k].firstarc.nextarc; while(p!=NULL) /*遍历Vk的出弧链表，将弧头顶点的入度减1*/ { j=p->adjvex; indegree[j]--; if(indegree[j]==0) EnSqqueue(&qu,j); /*入度是0的邻接顶点入队*/ p=p->nextarc; } free(indegree); DestroySqqueue(&qu);

50 七、拓扑排序和关键路径——关键路径(1) 【问题描述】某项工程包含有11项工作，这些工作之间的关系及工期安排如图6_21所示。图中弧代表工作，弧的权值代表某项工作的持续时间，比如a1需要持续6天，a8需要持续7天。顶点代表工作状态，比如V0代表工作开始，V2代表工作a2已完成，V4代表工作a4和a5已完成。问这项工程最短需要多少时间能完成。 用边来代表活动的网络，被称为AOE网 , AOE网通常用来估算一项工程的最短工期 入度为0的顶点，称为源点；出度为0的顶点，称为汇点。 源点到汇点的路径有多条，其中路径长度最长的被称为关键路径。工程的最短工期就是工程AOE网的关键路径的路径长度。

51 七、拓扑排序和关键路径——关键路径(2) 要想识别关键路径，我们必须引入2个量： 为了计算E(i)和L(i) ，我们需要再引入2个量：
活动ai的最早开始时间E(i)和最晚开始时间L(i)。 E(i) 和L(i)相等的活动被称为关键活动。由关键活动组成的路径，就是关键路径。 为了计算E(i)和L(i) ，我们需要再引入2个量： 顶点Vj的最早出现(发生)时间VE(j)和最晚出现(发生)时间VL(j)。 如果已知某活动ai对应的弧是<Vj,Vk>，那么就有 E(i)=VE(j)和L(i)=VL(k)-W(j,k)

52 七、拓扑排序和关键路径——关键路径(3) 如何计算VE(j)和VL(j)
⑴先计算顶点的VE值。我们假定源点的VE值是0，并且在逻辑上我们有： ⑵一旦求得所有顶点的VE值，我们就可以求得所有顶点的VL值。我们假定汇点的VL值就是它的VE值，即如果Vk是汇点，则有VL(k)=VE(k) 。而其他顶点的VL值的求解公式是：

53 七、拓扑排序和关键路径——关键路径(3) 【求关键路径的算法思想】 为了方便输出关键路径，可以将路径存储在一个链表中：
⑴先按照拓扑排序的顺序计算所有顶点的VE值：先将所有顶点的VE值初始化为0，当拓扑排序到Vj时，更新Vj邻接顶点的VE值。 ⑵再按照拓扑排序的逆序计算所有顶点的VL值：将所有顶点的VL值都初始化为汇点的VL值，当按照拓扑逆序的顺序遍历到Vj时，更新Vj的VL值。 ⑶根据顶点的VE值和VL值，计算弧的E值和L值，并判断是否是关键活动 为了方便输出关键路径，可以将路径存储在一个链表中： typedef struct pathnode { int fromvex,endvex; int weight; struct pathnode *next; }PATH;

54 七、拓扑排序和关键路径——关键路径(4) PATH* CriticalPath(ALGRAPH *alg)
{/*以邻接表为存储结构，求解AOE网的关键路径，返回存储关键路径的链表*/ int *indegree,*VE,*VL; PATH *Path,*TmpPath; int n,i,j,k,vl; ARCNODEPTR p; SQQUEUE qu; SQSTACK s; n=alg->vexnum;/*获得图的顶点数*/ indegree=(int *)malloc(n*sizeof(int));/*分配存储顶点入度的数组*/ if(indegree==NULL)return NULL; VE=(int *)malloc(n*sizeof(int));/*分配存储顶点VE值的数组*/ if(VE==NULL) return NULL; VL=(int *)malloc(n*sizeof(int));/*分配存储顶点VL值的数组*/ if(VL==NULL) return NULL; Path=(PATH *)malloc(sizeof(PATH));/*分配关键路径链表的头结点*/ if(Path==NULL)return NULL; Path->next=NULL;/*设置空链表*/

55 七、拓扑排序和关键路径——关键路径(5) for(i=0;i<n;i++) indegree[i]=0; /*初始化顶点入度为0*/
{ p=alg->vertices[i].firstarc.nextarc; while(p!=NULL) { indegree[p->adjvex]++; p=p->nextarc; } for(i=0;i<n;i++)VE[i]=0;/*初始化所有顶点的VE值为0*/ InitSqqueue(&qu,n);/*初始化队列，用于拓扑排序*/ InitSqstack(&s,n);/*初始化栈，用于获得拓扑逆序序列*/ for(i=0;i<n;i++) if(indegree[i]==0)EnSqqueue(&qu,i);/*源点入队*/

56 七、拓扑排序和关键路径——关键路径(6) while(!IsSqqueueEmpty(qu)) /*开始拓扑排序，同时计算顶点的VE值*/
{ DeSqqueue(&qu,&k);/*出队一个顶点Vk*/ Push(&s,k);/*将Vk入栈*/ p=alg->vertices[k].firstarc.nextarc; while(p!=NULL) /*遍历Vk的所有出弧，尝试更新弧头顶点的VE值，使之更大*/ { j=p->adjvex;/*Vj是Vk的一个弧头顶点*/ indegree[j]--;/*Vj的入度减1*/ if(indegree[j]==0) EnSqqueue(&qu,j); /*如果Vj的入度是0,将其入队*/ if(VE[k]+p->weight>VE[j])/*根据顶点Vk和弧<Vk，Vj>计算出来的VE值更大*/ VE[j]=VE[k]+p->weight;/*VE(j)取更大的值*/ p=p->nextarc; } free(indegree);/*不再需要indegree所指向的内存*/ DestroySqqueue(&qu);/*不再需要队列，销毁*/

57 七、拓扑排序和关键路径——关键路径(7) vl=VE[s.elem[s.top]];/*vl是汇点的VE值*/
for(i=0;i<n;i++) VL[i]=vl;/*将所有顶点的VL值初始化为汇点的VE值*/ while(!IsSqstackEmpty(s)) /*出栈的顺序就是拓扑排序的逆序顺序*/ { Pop(&s,&k);/*出栈顶点Vk*/ p=alg->vertices[k].firstarc.nextarc; while(p!=NULL) /*遍历Vk的所有出弧，更新Vk的VL值*/ { j=p->adjvex;/*Vj是Vk的一个弧头顶点*/ if(VL[j]-p->weight<VL[k])/*根据弧<Vk,Vj>计算的VL值更小*/ VL[k]=VL[j]-p->weight;/*VL(j)取更小值*/ p=p->nextarc; } DestroySqstack(&s);/*销毁栈*/

58 七、拓扑排序和关键路径——关键路径(8) for(i=0;i<n;i++) /*遍历所有顶点的出弧，寻找关键活动*/
{ p=alg->vertices[i].firstarc.nextarc; while(p!=NULL) { j=p->adjvex;/*找到一个弧<Vi,Vj>*/ if(VE[i]==VL[j]-p->weight) /*这个弧是关键活动*/ { TmpPath=(PATH*)malloc(sizeof(PATH));/*分配关键路径链表的结点*/ if(TmpPath==NULL) return NULL; TmpPath->fromvex=i;/*复制关键活动的信息*/ TmpPath->endvex=j; TmpPath->weight=p->weight; TmpPath->next=Path->next;/*将结点插入链表*/ Path->next=TmpPath; } p=p->nextarc; }//while(p } free(VE); free(VL); return Path;/*返回关键路径的链表*/

59 导航图(1)

60 导航图(2)

61 导航图(3)

62 导航图(4)

63 导航图(5)

64 导航图(6)

65 导航图(7)

66 导航图(8)

67 导航图(9)

68 导航图(10)

69 导航图(11)

70 导航图(12)

71 导航图(13)

72 导航图(14)