数据结构 第六章 图

第六章 图 知 识 点 图的逻辑结构特征及图的基本术语 邻接矩阵和邻接表两种图的存储结构的特点及适用范围 深度优先搜索和广度优先搜索两种遍历算法的特点和执行过程 生成树和最小生成树的概念及构造最小生成树的prim和kruskal算法 最短路径的含义及求最短路径的算法 拓扑排序的基本思想和步骤 关键路径法及其在管理科学中的作用 第六章 图

难 点 要 求 图的遍历、最小生成树、最短路径、拓朴排序算法的理解 关键路径法求关键活动和关键路径的方法 熟练掌握以下内容： 图的存储结构 图的遍历算法 了解以下内容： 图的最小生成树和求最小生成树算法的基本思想 带权有向图的最短路径问题 利用AOV网络的拓朴排序问题 利用AOE网络的关键路径法 第六章 图

第六章目录 6.1 图的定义和基本术语 6.2 图的存储方式 6.3 图的遍历 6.4 最小生成树 6.5 最短路径 6.6 拓扑排序 6.1 图的定义和基本术语 6.2 图的存储方式 6.3 图的遍历 6.4 最小生成树 6.5 最短路径 6.6 拓扑排序 6.7 关键路径法 6.8 应用实例与分析 小 结 习题与练习 第六章 图

6.1 图的定义和基本术语 图：图G由V（G）和E（G）这两个集合所组成，记为G=（V，E），其中V（G）是顶点（Vertex）的非空集，每个顶点可以标以不同的字符或数字；E（G）是边（Edge）的集合，特殊情况下E（G）可以是空集。每个边由其所连接的两个顶点表示。 无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。 有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。 第六章 图

图6.1 有向图与无向图 无向图G1 有向图G2 第六章 图

左图所示就是n=4的完全图，它一共有六条边。 完全图：在一个有n个顶点的无向图中，若每个顶点到其它（n-1）个顶点都连有一条边，则图中共有n(n-1)/2条边，这种图称为完全图（Complete graph，也称完备图）。 左图所示就是n=4的完全图，它一共有六条边。 第六章 图

权和网络：有些图， 对应每条边有一相应的数值，这个数值叫做该边的权(Weight)。边上带权的图称为带权图，也称为网络(Network)。 子图：设有两个图G =(V,E)和G’=(V’,E’)，若V(G’)是V(G)的子集，且E(G’)是E(G)的子集，则称G’是G的子图(Subgraph)。 例如图6.3所示的图是图6.1中G1的一些子图。 第六章 图

图6.3 子图 第六章 图

顶点的度：图中与每个顶点相连的边数，叫该顶点的度(Degree)。例如图6.1的图G1中，顶点①的度数为2，顶点②的度数为3，……。 第六章 图

路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。 路径：在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,…,Vm到达，Vq，则称顶点序列(Vp, V1,V2,…,Vm, Vq)为从Vp到Vq的路径(Path)。 路径长度：对于无权的图，路径长度指的是沿此路径上边的数目；对于有权图，一般是取沿路径各边的权之和作为此路径的长度。 若一条路径上各顶点均不重复，即路径经过每一顶点不超过一次，则此路径叫做简单路径。 如果从一个顶点出发又回到该顶点，即Vp与Vq相同，则此路径叫做环路（Cycle）。 第六章 图

连通、连通图：在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图(Connected graph)。 连通分量：例如图6.1中的图G1是连通图。图6.4中的图就是非连通图，非连通图的每一个极大连通子图叫连通分量(Connected Component)，此图包括二个连通分量。 第六章 图

图6.4 非连通图G 第六章 图

图6.1中的G2不是强连通图，它有两个强连通分量，如图6.5所示。 强连通图和强连通分量：在有向图G中，如果从顶点Vi到顶点Vj和从顶点Vj到顶点Vi之间都有路径，则称这两个顶点是强连通的。如果图中任何一对顶点都是强连通的，则此图叫做强连通图。非强连通图的每一个极大强连通子图叫做强连通分量。 图6.1中的G2不是强连通图，它有两个强连通分量，如图6.5所示。 第六章 图

图6.5 图G2的强连通分量 返回 第六章 图

6.2.1 邻接矩阵 邻接矩阵是表示顶点之间相邻关系的矩阵。所谓两顶点的相邻关系即它们之间有边相连。 邻接矩阵是一个（n×n）阶方阵，n为图的顶点数，它的每一行分别对应图的各个顶点，它的每一列也分别对应图的各个顶点。我们规定矩阵的元素为： 第六章 图

图6.6 无向图的邻接矩阵 第六章 图

图6.7 有向图的邻接矩阵 第六章 图

无向图的邻接矩阵是对称的，如果A[i，j]=1，必有A[j，i]=1。这说明，只输入和存储其上三角阵元素即可得到整个邻接矩阵。 邻接矩阵用二维数组即可存储，定义如下： int adjmatrix = ARRAY[n][n]; 如果图的各边是带权的，只需将矩阵中的各个1元素换成相应边的权即可。 第六章 图

产生无向图邻接矩阵算法 void creatgraph (int adjarray[ ][ ]) { int i,j,v1,v2,num; scanf (“%d”,&num); /*输入顶点数*/ if (num>0) for (i=1;i<=num;i++) for (j=1;j<=num;j++) adjarry [i][j]=0; /*矩阵初始化*/ do 第六章 图

产生无向图邻接矩阵算法续 scanf (“%d,%d”,&v1,&v2); /*输入边*/ adjarray[v1][v2]=1; } while(v1!=0 && v2!=0); } else num=0; retrun num; 第六章 图

6.2.2 邻接表 邻接表是图的一种链接存储结构。 在邻接表结构中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于该顶点Vi的边，即对于无向图每个结点表示与该顶点相邻接的一个顶点；对于有向图则表示以该顶点为起点的一条边的终点。 一个图的邻接矩阵表示是唯一的，但其邻接表表示是不唯一的。因为在邻接表的每个单链表中，各结点的顺序是任意的。 第六章 图

图6.8 邻接表 图6.6中无向图对应的邻接表 第六章 图

图6.7中有向图对应的邻接表 第六章 图

如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域。 在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。 邻接表中每个表结点均由两个域组成，其一是邻接点域（adjvex），用以存放与顶点Vi相邻接的顶点在图中的位置；其二是链域（next），用以指向依附于顶点Vi的下一条边所对应的结点。 如果用邻接表存放网络中的信息，则还需要在结点中增加一个存放权值的域。 在每个链表设一表头结点，一般这些表头结点本身以向量的形式存储。 第六章 图

对于无向图的邻接表来说，一条边对应两个单链表结点，邻接表结点总数是边数的2倍。 在无向图的邻接表中，各顶点对应的单链表的结点数（不算表头结点）就等于该顶点的度数。 在有向图邻接表中，一条弧对应一个表结点，表结点的数目和弧的数目相同。 在有向图邻接表中，单链表的结点数就等于相应顶点的出度数。 要求有向图中某顶点的入度数，需扫视邻接表的所有单链表，统计与顶点标号相应的结点个数。 第六章 图

邻接表存储结构定义 #define MAXVEX 30 struct edgenode { int adjvex ; /*邻接点域*/ struct edgenode *next ; /*链域*/ }; struct vexnode char data; /*顶点信息*/ struct edgenode *link; typedef struct vexnode adjlist[MAXVEX]; 第六章 图

产生无向图的邻接表算法 void creategraph (adjlist g) { int e,i,s,d,n; struct edgenode *p; printf(“请输入结点数(n)和边数(e):\n”); scanf(“%d,%d”,&n,&e); for(i=1;i<=n;i++) printf(“\n请输入第%d个顶点信息：”,i); scanf(“%c”,&g[i].data); g[i].link=NULL; } for(i=1;i<=e;i++) 第六章 图

产生无向图的邻接表算法续 { printf(“\n请输入第%d条边起点序号，终点序号：”,i); scanf(“%d,%d”,&s,&d); p=(struct edgenode *)malloc(sizeof(edgenode)); p→adjvex=d; /*邻接点序号为d*/ p→next=g[s].link; g[s].link=p; /*将新结点插入顶点Vs边表的头部*/ p→adjvex=s; /*邻接点序号为s*/ p→next=g[d].link; g[d].link=p; /*将新结点插入顶点Vd边表的头部*/ } 返回 第六章 图

6.3.1 深度优先搜索(DFS) 首先访问图中某指定起始点Vi ，然后由Vi出发访问它的任一相邻接顶点Vj，再从Vj出发访问Vj的任一未访问过的相邻接顶点Vk，再从Vk出发进行类似访问，如此进行下去，直到某顶点已没有未被访问过的相邻接顶点时，则退回一步，退到前一个顶点，找前一个顶点的其它尚未被访问的相邻接顶点。 如有未访问过的相邻接顶点，则访问此顶点后，再从该顶点出发向前进行与前述类似的访问； 如退回一步后，前一顶点也没有未被访问过的相邻接顶点，则再向回退一步进行搜索，重复上述过程，一直到所有顶点均被访问过为止。 第六章 图

图6.9 图的遍历例子 第六章 图

由于图中的路径可能有环路，为了避免重复访问某些顶点，设计图的搜索算法时，可设置一个表示顶点是否被访问过的辅助数组visited，初始时将数组元素置零，一旦某顶点Vi被访问过，则令visited[Vi ]=1，以后此顶点即不再访问。 第六章 图

深度优先搜索算法 深度优先搜索是一种递归的过程，可以简单地将其表示成递归的形式，其算法描述如下： DFS(V0) { 访问V0顶点; visited[V0]=1; 对所有与V0相邻接的顶点w if (visited[w]==0) DFS(w); } 第六章 图

邻接表表示的图的DFS算法 int visited[MAXVEX]; void dfsgraph(adjlist adj, int n) { int i; for(i=1;i<=n;i++) visited[i]=0; /*给visited数组赋初值*/ if(!visited[i]) dfs(adj, i); } 第六章 图

从Vi出发进行DFS的递归算法 void dfs(adjlist adj,int v) { struct edgenode *p; visited[v]=1; printf(“%d”,v); p=adj[v]→link; while(p!=NULL) if(visited[p→adjvex]==0) dfs(adjlist,p→adjvex); /*从v未访问的邻接点出发进行DFS*/ p=p→next; } 从Vi出发进行DFS的递归算法 第六章 图

时间复杂性分析 一个有n个顶点、e条边的图，在深度优先搜索图的过程中，找邻接点所需时间为O(e)。 对辅助数组初始化时间为O(n)。 因此，当用邻接表作为图的存储结构时，深度优先搜索图的时间复杂性为O(e+n)。 第六章 图

非递归算法 从顶点Vi出发进行深度优先遍历的递归过程也可以写成非递归的形式，此时需借助一个堆栈保存被访问过的结点，以便回溯时查找已被访问结点的未被访问过的邻接点。 设堆栈由一个一维数组构成，数组名为stack，栈顶指针为top ,假设此数组足够大,不必考虑溢出的可能。 第六章 图

非递归算法 #define MAXVEX 100 void dfs(adjlist g，int v,int n) { struct vexnode *stack[MAXVEX], *p; int visited[MAXVEX],top=0; for(i=1;i<=n;i++) visited[i]=0; printf(“%d”,v); p=g[v].link; visited[v]=1; while(top>0||p!=NULL) 非递归算法 第六章 图

非递归算法续 { while(p!=NULL) if (visited[p->adjvex]==1) p=p->next; else printf(“%d”,p->adjvex); visited[p->adjvex]=1; top++; stack[top]=p; p=g[p->adjvex].link; } 非递归算法续 第六章 图

非递归算法续 if(top>0) { top--; /*退栈，回溯查找已被访问结点的未被访问过的邻接点 */ p=stack[top]; p =p->next; } 非递归算法续 第六章 图

6.3.2 广度优先搜索(BFS) 图的广度优先搜索（BFS）类似于树的按层次遍历。 广度优先搜索的基本思想是：首先访问图中某指定的起始点Vi并将其标记为已访问过，然后由Vi出发访问与它相邻接的所有顶点Vj、 Vk……，并均标记为已访问过，然后再按照Vj、Vk……的次序，访问每一个顶点的所有未被访问过的邻接顶点，并均标记为已访问过，下一步再从这些顶点出发访问与它们相邻接的尚未被访问的顶点，如此做下去，直到所有的顶点均被访问过为止。 第六章 图

设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。 在广度优先搜索中，若对顶点V1的访问先于顶点V2的访问，则对V1邻接顶点的访问也先于V2邻接顶点的访问。就是说广度优先搜索中对邻接点的寻找具有“先进先出”的特性。因此，为了保证访问顶点的这种先后关系，需借助一个队列暂存那些刚访问过的顶点。 设此队列由一个一维数组构成，数组名为Queue，队首指针和队尾指针分别为front和rear。假设数组足够大，不必考虑有溢出的可能性。 广度优先搜索不是递归过程，不能用递归形式。 第六章 图

BFS算法描述 BFS(v0) { 访问v0顶点； visited[v0]=1; 被访问过的顶点入队； 当队列非空时，进行下面的循环 { （1）被访问过的顶点出队； （2）对所有与该顶点相邻接的顶点w if (visited[w]==0) { (a)访问w顶点； (b)visited[w]=1; (c)w入队; } BFS算法描述 第六章 图

邻接表表示的图的BFS算法 int visited[MAXVEX]; int queue[MAXVEX]; void bfs(adjlist adj,int v) { int front=0,rear=1,v; struct edgenode *p; visited[v]=1; printf(“%d”,v); queue[rear]=v; /*初始顶点入队*/ while(front!=rear) /*队列不为空*/ 第六章 图

邻接表表示的图的BFS算法续 { front=front+1; v=queue[front]; /*按访问次序出队列*/ p=adj[v]->link; /*找v的邻接顶点*/ while(p!=NULL) if (visited[p->adjvex]==0) visited[p->adjvex]=1; printf(“%d”,p->adjvex); 第六章 图

邻接表表示的图的BFS算法续 rear=rear+1; queue[rear]=p->adjvex; } p=p->next; 第六章 图

时间复杂性分析 一个有n个顶点、e条边的图，在广度优先搜索图的过程中，每个顶点至多进一次队列，图的搜索过程实质上是通过边来找顶点的过程，找邻接点所需时间为O(e)。 对辅助数组初始化时间为O(n)。 因此，当用邻接表作为图的存储结构时，广度优先搜索图的时间复杂性为O(e+n)。 返回 第六章 图

6.4 最小生成树 在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，若边集E(G’)中的边刚好将图的所有顶点连通但又不形成环路，我们就称子图G’是原图G的生成树（Spanning tree）。 生成树有如下特点：任意两个顶点之间有且仅有一条路径；如果再增加一条边就会出现环路；如果去掉一条边此子图就会变成非连通图。 一个有n 个顶点的完全图，一共存在n(n-2)种不同的生成树。 第六章 图

具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路） 。 对于带权的连通图（连通网）G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树（Minimum Spanning Tree）。 具有n个顶点的连通图的生成树具有n-1条边（少于此边数不可能将各顶点连通，多于此边数则必然要出现环路） 。 第六章 图

图6.10 图G 及其生成树 无向连通图 G 生成树 第六章 图

图6.10 图G 及其生成树 生成树 最小生成树 第六章 图

6.4.1 普里姆(prim)算法 假设G=(V,E)是一个具有n 个顶点的连通网络，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空。 算法开始时，首先从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U={V1}； 然后从那些其一个端点已在U中，另一个端点仍在U外的所有边中，找一条最短（即权值最小）的边，假定该边为(Vi,Vj),其中Vi∈U，Vj∈V-U,并把该边(Vi,Vj)和顶点Vj分别并入T的边集TE和顶点集U； 第六章 图

如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n 个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边； 第六章 图

图6.11 普里姆算法例子 第六章 图

开始，由于U的初值为{1}，所以，closest[i]的值为1，i=2,…n,而lowcost[i]为V1到各顶点的边中最小的权值。 为了便于在顶点集合U和V-U之间选择权最小的边，建立两个数组closest和lowcost,closest[i]表示U中的一个顶点，该顶点与V-U中的一个顶点构成的边具有最小的权；lowcost表示该边对应的权值。 开始，由于U的初值为{1}，所以，closest[i]的值为1，i=2,…n,而lowcost[i]为V1到各顶点的边中最小的权值。 第六章 图

普里姆算法 void prim(int c[MAXVEX], int n) /*c表示图的邻接矩阵，图的顶点为{1,2…n}*/ { int lowcost[n],closest[n]; int i,j k,min; for(i=2,i<=n;i++) /*从顶点V1开始*/ lowcost[i]=c[1][i]; closest[i]=1; } for(i=2;i<=n;i++) /* 从U之外求离U中某顶点最近的顶点*/ 普里姆算法 第六章 图

普里姆算法续 { min=lowcost[i]; k=i; for(j=2;j<=n;j++) if (lowcost[j]<min) min=lowcost[j]; k=j; } printf(“(%d,%d)”,k,closest[j]); /* 打印生成树的一条边*/ 普里姆算法续 第六章 图

普里姆算法续 lowcost[k]=32767; /* k加入 到U中 */ for(j=2;j<=n;j++) if (c[k][j]<lowcost[j] && lowcost[j]<32767) { lowcost[j]=c[k][j]; closest[j]=k; } 普里姆算法续 第六章 图

算法分析 该算法中每一步执行都要扫描数组lowcost，在V-U顶点集中找出与U最近的顶点，令其为k，并打印边（k,closest[k]）。 然后将k加入U顶点集合中，并修改数组lowcost和closest。 这里用c表示图的邻接矩阵，c[i][j]和c[j][i]是边(i,j)的权。 第六章 图

6.4.2 克鲁斯卡尔（Kruskal）算法 假设G =（V，E）是一个具有n个顶点的连通网络，T=(U,TE)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，TE的初值为空集。 基本思想：将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成环路，则把它并入TE中，保留作为生成树T的一条边，若选取的边使生成树T形成环路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止。此时的T即为最小生成树。 第六章 图

现以图6.12中(a)图为例说明此算法。 设此图是用边集数组表示的，边集数组是一个结构数组，数组中的每个元素表示一条边，组成每条边的是三元组序列（边的起始顶点、边的终止顶点、边的权值）。 将每条边的数据输入之后，按权值的大小进行了排序，如图6.12(b) 所示。这样，按权值由小到大选取各边就是在数组中按下标由1到e(图中边的数目)的次序选取。 第六章 图

图6.12 克鲁斯卡尔算法例子 (a)带权图 第六章 图

(b)边集数组 第六章 图

(c)最小生成树 第六章 图

在选取某边时如何判断是否与已保留的边形成环路？克鲁斯卡尔算法是通过将各顶点划分为集合的办法来解决的。 开始时假定n 个顶点分属于n 个集合，即每个集合中有一个顶点，当确定某条边保留作为生成树的一条边时，就将该边两端点所属的两集合合并为一个，表示原来属于两个集合的各个顶点已被这条新的边连通。如果取到某条边，发现它的两个端点已属于同一集合时，此边则应当舍去。因为两个顶点属于同一集合说明它们已连通，若再添上这条边就会出现环路。 第六章 图

如此进行下去，到所有的顶点均已属于一个集合时，此最小生成树就构成了。 用一个set[ ]数组来表示顶点，set的初值为s[i]=0(i=1,2,…,n),表示各顶点自成一个分量。当从边集数组中按次序选取一条边时，查找它的两个顶点所属的分量，当这两个分量不相等，则表明所选的这条边的两个顶点分属不同的集合，该边加入到生成树中不会形成环路，应作为生成树的一条边，同时合并这两个分量为一个连通分量。若这两个分量相等，则表明这条边的两个顶点同属一个集合，将此边加入到生成树必产生环路，应予放弃。 第六章 图

利用克鲁斯卡尔构造最小生成树的边集数组结构定义如下： # define MAXE 100 struct edges /* 边集类型，存储一边条的起始顶点为bv,终止顶点为tv和权w */ { int bv,tv,w; } typedef struct edges edgeset[MAXE]; 第六章 图

int seeks(int set[],int v) { int i=v; while(set[i]>0) i=set[i]; 查找一个顶点所属的分量函数如下： int seeks(int set[],int v) { int i=v; while(set[i]>0) i=set[i]; return(i); } 第六章 图

克鲁斯卡尔算法 void kruskal (edgeset ge, int n, int e) /* ge为权按从小到大排序的边集数组 */ { int set[MAXE], v1, v2, i, j; for (i=1;i<=n;i++) set[i]=0; /*给set中每个元素赋初值*/ i=1; /* i表示获取的生成树中的边数，初值为1*/ j=1; /* j表示ge中的下标，初始值为1*/ while (j<n && i<=e) /* 检查该边是否加入到生成树中*/ v1=seeks(set,ge[i].bv); 克鲁斯卡尔算法 第六章 图

克鲁斯卡尔算法续 v2=seeks(set,ge[i].tv); if (v1!=v2) /* 当 v1,v2不在同一集合，该边加入生成树*/ { printf(“(%d,%d)”,ge[i].bv,ge[i].tv); set[v1]=v2; j++; } i++; 克鲁斯卡尔算法续 返回 第六章 图

6.5 最短路径 所谓最短路径（shortest path）问题指的是：如果从图中某顶点出发（此点称为源点），经图的边到达另一顶点（称为终点）的路径不止一条，如何找到一条路径使沿此路径上各边的权值之和为最小。 设一有向网络G =（V,E），已知各边的权值，并设每边的权均大于零，以某指定V0为源点，求从V0到图的其余各点的最短路径。 以图 6.13为例，若指定以顶点V6为源点V0，该图比较简单，通过观察可得到从V6到其余各点的最短路径。 第六章 图

图6.13 最短路径例子 第六章 图

狄克斯特拉算法 狄克斯特拉于1959年提出了一个按路径“长度”递增的次序，逐步得到由给定源点到图的其余各点间的最短路径的算法。 假设我们以邻接矩阵cost表示所研究的有向图，cost[i][j]表示有向边<i,j>对应权值，如果两点之间无相应方向的边，则该元素取为无穷大。在计算机中此矩阵用一个（n×n）二维数组表示（n为图的顶点数），无穷大元素则可用某很大的有限值（如32767）代替。 第六章 图

图6.13对应的邻接矩阵 第六章 图

集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素S[i]为0，否则为1。 狄克斯特拉算法需要一个顶点集合，初始时集合内只有一个源点V0 ，以后陆续将已求得最短路径的顶点加入到集合中，到全部顶点都进入集合了，过程就结束了。 集合可用一维数组来表示，设此数组为S，凡在集合S以外的顶点，其相应的数组元素S[i]为0，否则为1。 还需要另一个一维数组dist，每个顶点对应数组的一个单元，记录从源点到其他各顶点当前的最短路径长度，其初值为dist[i]=cost[V0][i]，i=2…n。数组dist中的数据随着算法的逐步进行要不断地修改。 第六章 图

重复上述过程，直到S中包含V中其余各顶点的最短路径。 定义了S集合和dist数组并对其初始化后，狄克斯特拉算法在进行中，都是从S之外的顶点集合中选出一个顶点w，使dist[w]的值最小。于是从源点到达w只通过S中的顶点，把w加入集合S中，并调整dist中记录的从源点到集合中每个顶点v的距离：从原来的dist[v]和dist[w]+cost[w][v]中，选择较小的值作为新的dist[v]。 重复上述过程，直到S中包含V中其余各顶点的最短路径。 第六章 图

狄克斯特拉算法 #define MAXVEX 100 /* 定义最多顶点数 */ void shortpath ( int cost[MAXVEX][MAXVEX], dist[MAXVEX], n, v0) { int s[MAXVEX], u, vnum, w, wm; for(w=1;w<=n;w++) /*最短路径初始化*/ dist[w]=cost[v0][w]; } for(w=1;w<=n;w++) s[w]=0; s[v0]=1; /*S中顶点个数的初值*/ vnum=1; 狄克斯特拉算法 第六章 图

狄克斯特拉算法续 while(vnum<n-1) /*最后一个顶点已无选择余地*/ { wm=32767; u=v0; for(w=1;w<=n;w++) if (s[w]==0 && dist[w]<wm) u=w; wm=dist[w]; /* 找最小dist[w] */ } s[u]=1; /*u为找到最短路径的终点*/ vnum++; 狄克斯特拉算法续 第六章 图

狄克斯特拉算法续 for(w=1;w<=n;w++) if (s[w]==0 && dist[u]+cost[u][w] < dist[w]) { dist[w]=dist[u]+cost[u][w]; }/*调整不在S集合中的顶点的最短路径*/ } printf(“%d”,w); printf(“%d”,dist[i]); } /* 输出结果 */ 狄克斯特拉算法续 第六章 图

狄克斯特拉算法例子 以图6.13所示的图为例来说明当指定以V6为源点V0后，用狄克斯特拉算法求最短路径的动态执行情况，其表示集合的数组S和表示距离的数组dist元素值的变化如图6.14所示。 第六章 图

图6.14 算法动态执行情况 第六章 图

返回 第六章 图

6.6 拓扑排序 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： ①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目； ②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。 在工厂中，一件设备的生产包括许多工序，各工序之间也存在这两种关系。 学校里某个专业的课程学习，有些课程是基础课，它们可以独立于其它课程，即无前导课程；有些课程必须在一些课程学完后才能开始学。 第六章 图

这些类似的问题都可以用有向图来表示，我们把这些子项目、工序、课程看成一个个顶点称之为活动(Activity)。 如果从顶点Vi到Vj之间存在有向边< Vi，Vj>,则表示活动i必须先于活动j进行。这种图称做顶点表示活动的网络(Activity On Vertex network,简称AOV网络)。 例如图6.15是某校计算机专业的课程及其相互之间的关系，它对应的AOV网络如图6.16所示。 第六章 图

图6.15 某专业课程设置 第六章 图

图6.16 AOV网络 第六章 图

因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。 在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。 AOV网络中一定不能有有向环路。例如在图6.17那样的有向环路中，V2是V3的前趋顶点，V1是V2的前趋顶点，V3又是V1的前趋顶点，环路表示顶点之间的先后关系进入了死循环。 因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应用中才有实际意义。 第六章 图

图6.17 有向环路 第六章 图

拓扑排序 所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。 通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。 第六章 图

拓扑排序方法 (1) 在网络中选择一个没有前趋的顶点，并把它输出； (2) 从网络中删去该顶点和从该顶点发出的所有有向边； (3) 重复执行上述两步，直到网中所有的顶点都被输出 (此时，原AOV网络中的所有顶点和边就都被删除掉了)。 如果进行到某一步，无法找到无前趋的顶点，则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。 第六章 图

图6.18 拓扑排序过程 AOV网络 输出V3后 第六章 图

输出V4后 输出V2后 输出V1后 输出V5后 第六章 图

为了实现拓扑排序的算法，对于给定的有向图，假定采用邻接表作为它的存储结构，每个顶点在邻接表中对应一个单链表，表示该顶点的各直接后继顶点。 规定将每个结点的Data域改为int型，并将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。 例如图6.18有向图生成的邻接表如图6.19所示。 第六章 图

图6.19 AOV网络的邻接表 第六章 图

在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。 删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。 设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。 第六章 图

设计算法时，可借用表头结点的Data域构成一个链接堆栈。用该数据域存放下一个入度为零的顶点标号，将堆栈中的各个单元链接起来，再设置一个栈顶指针top即可。 右图为表示图6.19的链接堆栈。 第六章 图

用邻接表存储AOV网络，实现拓扑排序的步骤可描述如下： (1) 把邻接表中所有入度为零的顶点进栈； (2) 在栈不空时： ①退栈并输出栈顶的顶点j； ②在邻接表的第i个单链表中，查找顶点为j的所有直接后继顶点k，并将顶点k的入度减1。若顶点k的入度为零，则顶点k进栈； ③若栈空时输出的顶点个数不是n,则有向图中有环路，否则拓扑排序完毕。 第六章 图

拓扑排序算法 void topsort(adjlist adj, int n) /*adj为邻接表*/ { int num,i,j,top; struct vexnode *q; top=0; num=0; /*num指示输出顶点个数*/ for(i=1;i<=n;i++)/*建立入度为0顶点的堆栈*/ if(adj[i]->data==0) adj[i]->data=top; top=i; } 拓扑排序算法 第六章 图

拓扑排序算法续 while(top>0) { i=top; top=adj[i]->data; /*在链表中删除入度为0的顶点，顶点序号为i*/ q=adj[i]->link; printf(“%d”,i); /*输出顶点Vi并计数*/ num++; while(q!=NULL) j=q->adjvex; adj[j]->data--; /*将后继结点j的入度减1*/ 拓扑排序算法续 第六章 图

拓扑排序算法续 if(adj[j]->data==0) { adj[j]->data=top; top=j; } q=p->next; /*找下一个后继结点*/ if(num<n) printf(“网络中有环路! ”\n); /*因输出的顶点数小于n*/ 拓扑排序算法续 返回 第六章 图

6.7 关键路径法 关键路径法是采用边表示活动(Activity On Edge)的网络，简称为AOE网络。 AOE网络是一个带权的有向无环路图，其中，每个顶点代表一个事件(Event)，事件说明某些活动或某一项活动的完成，即阶段性的结果。 离开某顶点的各条边所代表的活动，只有在该顶点对应的事件出现后才能开始。 权值表示活动持续的时间。 第六章 图

图6.20 一个AOE网络 第六章 图

AOE网络 通常利用AOE网络可以研究以下两个问题： (1) 完成整个工程至少需要多少时间？ (2) 哪些活动是影响工程进度的关键？ 第六章 图

关键路径 完成工程所需的时间就是从开始点起进行到结束点止所需的时间。 路径长度是指沿路径各边的权值之和，也就是这些边所代表的活动所需时间之和。 完成整个工程所需的时间取决于从开始点到结束点的最长路径长度，此长度最大的路径叫做关键路径。 分析关键路径的目的是辨别哪些是关键活动，以便争取提高关键活动的效率，缩短整个工期。 第六章 图

在描述关键路径的算法时，设活动ai由弧<j,k>表示，要确定如下几个相关的量： (1) 事件Vj的最早出现时间和活动的最早开始时间：从源点V1到某顶点Vj的最长路径长度叫作事件j的最早出现时间，表示成ev[j]。顶点Vj的最早出现时间ev[j]决定了从Vj指出的各条边所代表活动的最早开始时间，因为事件j不出现，它后面的各项活动就不能开始。我们以e[i]表示活动ai的最早开始时间。显然e[i]= ev[j] 。 第六章 图

(2) 活动ai的最迟开始时间：在不影响整个工程按时完成的前提下，此项活动最迟的必须开始时间，表示成L[i]。 只要某活动ai有L[i]=e[i]的关系，我们就称ai为关键活动。关键活动只允许在一个确定的时间开始，再早，它前面的事件还没出现，尚不能开始；再晚，又会延误整个工程的按时完成。由于完成整个工程所需的时间是由关键路径上各边权值之和所决定的，显然关键路径上各条边所对应的活动都是关键活动。 第六章 图

L[i]= Lv[j]-(活动ai所需时间) 也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。 (3) 事件j的最迟出现时间：即事件j在不延误整个工程的前提下允许发生的最迟时间，表示为Lv[j]。对某条指向顶点Vj的边所代表的活动ai可得到： L[i]= Lv[j]-(活动ai所需时间) 也就是活动ai必须先于它后面事件的最迟出现时间开始，提前的时间为进行此活动所需的时间。 图6.21所示为活动开始时间与事件出现时间的关系。 第六章 图

图6.21 活动开始时间与事件出现时间的关系 第六章 图

确定关键路径的方法就是要确定e[i]=L[i]的关键活动。 假设以w[j,k]表示有向边<j,k>的权，即此边对应的活动所需的时间，为了求AOE网络中活动ai的最早开始时间e[i]和活动ai的最迟开始时间L[i]，先要求得顶点Vk的事件Vk的最早出现时间ev[k]和最迟出现时间Lv[k] 。 第六章 图

ev[k]和Lv[k]可以采用下面的递推公式计算： (1) 向汇点递推 由源点的ev[1]=0开始，利用公式： 向汇点的方向递推，可逐个求出各顶点的ev 。式中p表示所有指向顶点的边的集合，如图6.22所示。 第六章 图

图6.22 集合p 此式的意义为：从指向顶点Vk的各边的活动中取最晚完成的一个活动的完成时间作为Vk的最早出现时间ev[k]。 第六章 图

向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表示所有由Vj点指出的边的集合，如图6.23所示。 (2) 向源点递推 由上一步的递推，最后总可求出汇点的最早出现时间ev[n]。因汇点就是结束点，最迟出现时间与最早出现时间相同，即Lv[n]=ev[n]。从汇点的最迟出现时间Lv[n]开始，利用下面公式： 向源点的方向往回递推，可逐个求出各顶点的最迟出现时间Lv。式中s表示所有由Vj点指出的边的集合，如图6.23所示。 第六章 图

图6.23 集合s 此公式的意义为：由从Vj顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vj的最迟出现时间。 第六章 图

无论是向汇点递推还是向源点递推，都必须按一定的顶点顺序进行。 对所有的有向边，向汇点递推是先求出尾顶点的ev值，再求头顶点的ev值；向源点递推则相反，先求头顶点的Lv值，再求尾顶点的Lv值。 为此，可利用上节介绍的拓扑排序得到的顶点次序进行向汇点的递推，向源点的递推按相反的顺序进行即可，不必再重新排序。 第六章 图

关键路径算法 (1) 输入e条有向边<j,k>，建立AOE网络的存储结构； (2) 从源点出发，令ev[1] =0，按拓扑排序的序列求其余各顶点的最早出现时间ev[i](2≤i≤n)。若拓扑排序序列中的顶点个数小于网络中的顶点数n，则说明网络中存在环路，算法中止执行；否则执行(3)； 第六章 图

(3) 从汇点Vn出发，令Lv[n]=ev[n]，按逆拓扑排序的序列求其余各顶点的最迟出现时间 Lv[i](n-1≥i≥1)； (4) 根据各顶点的ev和Lv值求每条有向边ai的最早开始时间e[i]和最迟开始时间L[i]。若某有向边ai满足e[i]=L[i],则为关键活动。 对图6.20例子中的AOE网络，各事件的最早出现时间和最迟出现时间及各活动的最早开始时间和最迟开始时间计算结果如表6.1所示。 第六章 图

表6.1 AOE网络中的关键活动 第六章 图

由表6.1可知时间余量为零的活动都是关键活动，即为a1，a4，a7，a8，a10，a11。 这些关键活动构成两条关键路径，即关键路径(V1，V2，V5，V7，V9)和(V1，V2，V5，V8，V9)。 在安排工程时，对于关键活动和余量小的活动应重点保证，余量较大的活动可适当地放松些，对非关键活动加速进行，并不能使整个工程提前完成，只有提高关键路径上的活动的效率，才能缩短整个工程的工期。 返回 第六章 图

例8.1 已知一有向图的邻接表存储结构如图6.24所示，分别给出从顶点v1出发进行深度优先和广度优先遍历所得到的顶点序列。 第六章 图

图6.24 一个有向图的邻接表 第六章 图

例8.1解答 解：根据有向图的深度优先遍历算法，从顶点v1出发所得到的顶点序列是： v1，v3，v4，v5，v2 第六章 图

例8.2 有n个顶点的无向图或有向图采用邻接矩阵和邻接表表示，请回答下列问题: (1) 如何计算图中有多少条边？ (2) 如何判断任意两个顶点i和j是否有边相连？ (3) 如何计算任意一个顶点的度是多少？ 第六章 图

例8.2解答 解：(1) 对于无向图邻接矩阵中“1”的个数除2为图的边数。邻接表中的各单链表中的结点数除2为图的边数。 对于有向图邻接矩阵中“1”的个数为图的边数。邻接表中的各单链表中的结点数为图的边数。 (2) 对于无向图，在邻接矩阵中第i行第j列元素为“1”，或者第j行第i列元素为“1”，则顶点i与j有边相连。在邻接表中的第i个单链表中有结点为j，或者第j个单链表中有结点为i，则顶点i与j有边相连。 第六章 图

对于有向图，在邻接矩阵中第i行第j列元素为“1”，则有一条从i到j的边。在邻接表中的第i个单链表中有结点为j，则有一条从i到j的边。 (3)对于无向图邻接矩阵中第i行的元素之和为i顶点的度，邻接表中的第i个单链表中的结点数为i顶点的度。 对于有向图邻接矩阵中第i行元素之和为i顶点的入度，第j列元素之和为j顶点的出度。在邻接表中，第i个单链表的结点数就是i顶点的出度，整个邻接表中具有的结点为i的结点数就是i顶点的入度。 返回 第六章 图

小 结 图 图的存储结构 图的遍历 图的应用 邻接矩阵 邻接表 深度优先搜索 广度优先搜索 最小生成树 最短路径问题 小 结 图 图的存储结构 邻接矩阵 邻接表 图的遍历 深度优先搜索 广度优先搜索 图的应用 最小生成树 最短路径问题 利用AOV网络研究拓扑排序问题 利用AOE网络研究关键路径的方法 返回 第六章 图

习题与练习 一、基本知识题 1. 图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？ 2. 什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？ 3. 给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。 第六章 图

图6.25 一个无向图G 第六章 图

4. 假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。 第六章 图

图6.26 一个无向图G 5. 分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。 第六章 图

图6.27 一个带权连通图G 6. 应用prim算法求图6.27所示带权连通图的最小生成树。 第六章 图

图6.28 一个有向图G 7. 写出图6.28所示有向图的拓朴排序序列。 第六章 图

二、算法设计题 1. 如图6.29所示图G，试给出其对应的邻接表，并写出深度优先算法。 3. 编写一个函数通过与用户交互建立一个有向图的邻接表。 4. 编写一个无向图的邻接矩阵转换成邻接表的算法。 第六章 图

图6.29 一个无向图G 第六章 图

5. 已知一个有n个顶点的有向图的邻接表，设计算法分别实现 1) 求出图中每个顶点的出度。 2) 求出图中每个顶点的入度。 3) 求出图中出度最大的一个顶点，输出其顶点序号。 4) 计算图中出度为0的顶点个数。 返回 第六章 图