《数据结构实用教程（C语言版）》课件第6章 图

第6章图本章中介绍下列主要内容：图的定义图的存储结构图的遍历操作图的几个典型问题本章目录6.1图的基本概念16.2图的存储结构26.3图的遍历36.4最小生成树46.5拓扑排序56.6AOE网与关键路径6结束6.7最短路径问题76.1图的基本概念6.1.1图的定义6.1.2图的基本术语6.1.3

图的基本操作返回到总目录6.1.1图的定义图是由一个非空的顶点集合和一个描述顶点之间关系即边（或者弧）的集合组成，它可以定义为一个二元组：G=(V,E)其中，G表示一个图，V表示图G中全部顶点组成的非空集合，E是图G中全部边组成的集合。按照图中边是否有方向性，图分为有向图和无向图两类。图6-1（a）表示的是无向图，图6-1（b）表示的是有向图。返回到本节目录有向图和无向图的示例（a）无向图G1

（b）有向图G2图6-1图的类型返回到本节目录有向图和无向图的边的表示在无向图中，用圆括号表示两个顶点之间的边。（vi,vj）表示顶点vi和顶点vj

之间连线表示的边。若图中边有方向，则用尖括号表示两个顶点之间的首尾关系，有向边也称为弧。在有向边<vi,vj>中，vi称为弧尾，vj称为弧头。返回到本节目录6.1.2图的基本术语1．无向图（Undigraph）

在一个图中，如果每条边都没有方向（如图6-1（a）所示），则称该图为无向图。2．有向图（Digraph）在一个图中，如果每条边都有方向（如图6-1（b）所示），则称该图为有向图。3．无向完全图在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。如图6-2（a），可以证明，在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

返回到本节目录6.1.2图的基本术语4．有向完全图在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。如图6-2（b），在一个含有n个顶点的有向完全图中，有n(n-1)条弧。5．顶点的度、入度、出度在无向图中：一个顶点拥有的边数，称为该顶点的度。记为TD(v)。返回到本节目录6.1.2图的基本术语在有向图中：

（a）一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；

（b）一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；

（c）一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。返回到本节目录6.1.2图的基本术语6．权图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight）。7．网——边(或弧)上带权的图称为网(Network)。如果每一条边都有与它相关的数，称为权，我们将这种带权的图叫做网。如果图中边是无方向的带权图，则图是一个无向网；如果图中边是有方向的带权图，则就是一个有向网。返回到本节目录6.1.2图的基本术语8．路径、路径长度顶点vi到顶点vj之间的路径是指顶点序列vi，vk1，vk2，…，vkm，vj.。其中：（vi,vk1），(vk1,vk2)，…，(vkm,.vj)分别为图中的边。路径上边或弧的数目称为路径长度。在图6-1（a）的无向图G1中，v1→v3→v4→v5与v1→v2→v5是从顶点v1

到顶点v5

的两条路径，路径长度分别为3和2。返回到本节目录6.1.2图的基本术语9．回路或环在一个路径中，若其第一个顶点和最后一个顶点是相同的，则称该路径为一个回路或环。10．简单路径若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。如图6-1（a）中的v1→v3→v4。11．简单回路除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。返回到本节目录6.1.2图的基本术语12．稀疏图对于有很少条边的图(e<nlog2n，e为边数，n为顶点数)称为稀疏图，反之称为稠密图。13．子图对于图G=（V，E），G′=（V′，E′），若存在V′是V的子集，E′是E的子集，则称图G′是G的一个子图。14．连通图、连通分量在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。任意两顶点都是连通的图称为连通图。无向图的极大连通子图称为连通分量。返回到本节目录6.1.2图的基本术语15．强连通图、强连通分量对于有向图来说，若图中任意一对顶点vi

和vj(i≠j)均有从一个顶点vi到另一个顶点vj有路径，也有从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。16．生成树连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树（SpanningTree）。在生成树中添加任意一条属于原图中的边必定会产生回路,n个顶点的生成树具有n-1条边。返回到本节目录6.1.3

图的基本操作图的基本操作有：（1）CreatGraph(G)：输入图G的顶点和边，建立图G的存储。（2）DFSTraverse(G，v)：在图G中，从顶点v出发深度优先遍历图G。（3）BFSTtaverse(G，v)：在图G中，从顶点v出发广度优先遍历图G。

返回到本节目录6.2图的存储结构6.2.1邻接矩阵6.2.2邻接表返回到总目录6.2.1邻接矩阵1．图的邻接矩阵图的邻接矩阵是使用顺序结构存储图。假设图G＝（V，E）有n个顶点，即V＝{v0,v1,…,vn-1}，则G的邻接矩阵是具有如下性质的n阶方阵：A[i][j]=1

若(vi,vj)或<vi,vj>是E(G)中的边

0

若(vi,vj)或<vi,vj>不是E(G)中的边返回到本节目录（a）G1的邻接矩阵（b）G2的邻接矩阵图6-6图6-1的邻接矩阵返回到本节目录2．网的邻接矩阵若G是网，则邻接矩阵可定义为：

wij

若(vi,vj)或<vi,vj>是E(G)中的边

A[i][j]=0若i=j时

∞

若(vi,vj)或<vi,vj>不是E(G)中的边其中，wij表示边(vi,vj)或<vi,vj>上的权值；∞表示一个计算机允许的、大于所有边的权值的数。图6-7（a）所示的无向网G4用邻接矩阵表示法如图6-7（b）所示；返回到本节目录（a）无向网G4的示意图（b）无向网G4的邻接矩阵图6-7网和网的邻接矩阵返回到本节目录3．图的邻接矩阵表示法的特点（1）无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。（2）对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的非零元素的个数。（3）对于有向图，顶点vi的度是邻接矩阵中第i行和第i列的非零元素的个数之和。（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连，但要确定图中的边数，则必须按行、按列对每个元素进行检查，所花费的时间代价很大。这是邻接矩阵存储图的局限性。返回到本节目录4．建立一个图的邻接矩阵的算法（1）以邻接矩阵存储图顶点间的关系定义图的一种存储结构。#defineMAXVEX100/*图中最大顶点个数*/typedefcharVertexType[3];/*定义VertexType为char数组类型*/typedefstructvertex{intadjvex;/*顶点编号*/VertexTypedata;/*顶点的信息*/}VType;/*顶点类型*/返回到本节目录typedefstructgraph{intn,e;/*n为实际顶点数，e为实际边数*/VTypevexs[MAXVEX];/*顶点集合*/intedges[MAXVEX][MAXVEX];/*边的集合*/}AdjMatix;/*图的邻接矩阵类型*/返回到本节目录（2）用邻接矩阵为存储结构建立图的算法（如算法6.1）。

算法6.1intCreateMatix(AdjMatix*g){inti,j,k,b,t,e;intw;printf("\n顶点数(n))和边数(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("序号为%d的顶点信息：",i);scanf("%s",g->vexs[i].data);g->vexs[i].adjvex=i;}返回到本节目录for(i=0;i<g->n;i++)for(j=0;j<g->n;j++)g->edges[i][j]=0;/*将邻接矩阵元素全部置0*/for(k=0;k<g->e;k++){printf("序号为%d的边=>",k);printf("起点号终点号

权值：");scanf("%d%d%d",&b,&t,&w);/*输入行数，列数和权值*/

返回到本节目录if(b<g->n&&t<g->n&&w>0)g->edges[b][t]=w;/*将b行、t列权值w存入邻接矩阵*/else{printf("\n输入错误！");return(0);}}return(1);}返回到本节目录6.2.2邻接表1．图的邻接表邻接表(AdjacencyList)是图的一种顺序存储与链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，该方法将所有邻接于vi的顶点vj连成一个单链表，这个单链表就称为顶点vi的邻接表。再将所有点的邻接表表头放到数组中，就构成了图的邻接表。在邻接表表示中有两种结点结构，如图6-8所示。返回到本节目录图6-8邻接矩阵表示的结点结构对于网的边表需再增设一个存储边上信息（如权值等）的域（info），网的边表结构如图6-9所示。图6-9

网的边表结构返回到本节目录

图6-1（a）中的图G1和（b）中的图G2的邻接表如图6-10（a）、（b）所示。为了便于确定顶点i的入度或以顶点i为头的弧，可以建立一个逆邻接表。逆邻接表是对每个顶点i建立一个链接以它为头的弧尾顶点的链表。图6-9（c）就是图6-1（b）中图G2逆邻接表。图G1的邻接表（b）图G2的邻接表（c）图G2的逆邻接表图6-10图的邻接表返回到本节目录2．图的邻接表表示法的特点（1）无向图中若有n个顶点、e条边，则它的邻接表需要n个表头指针和2e个边结点。而有向图中有n个顶点、e条边，则它的邻接表需要n个表头指针和e个边结点。（2）对于无向图，顶点vi的度是第i个链表的结点数。（3）对于有向图，顶点vi的出度是第i个链表的结点数，而求入度则必须遍历整个邻接表，即在所有链表中找邻接点域的值为i的边结点的个数。所以，对于那些需要经常查找顶点入边或入边邻接点的运算，为此专门建立一个逆邻接表，该表中每个顶点的单链表存储所有入边的信息。返回到本节目录3．建立邻接表的算法

(1)下面先给出一个以邻接表为存储结构的图类型（ALGRAPH）定义:#defineNULL0/*NULL为空指针*/#defineMAXVEX100/*数组最大元素个数*/typedefcharVertexType[3];typedefstructedgenode{intadjvex;/*邻接点序号*/intvalue;/*边的权值*/structedgenode*next;/*下一条边的顶点*/}ArcNode;/*每个顶点建立的单链表中结点的类型*/返回到本节目录typedefstructvexnode{VertexTypedata;/*结点信息*/ArcNode*firstarc;/*指向第一条边结点*/}VHeadNode;/*单链表的头结点类型*/typedefstruct{intn,e;/*n为实际顶点数，e为实际边数*/VHeadNodeadjlist[MAXVEX];/*单链表头结点数组*/}AdjList;/*图的邻接表类型*/返回到本节目录2．图的邻接表表示法的特点（1）无向图中若有n个顶点、e条边，则它的邻接表需要n个表头指针和2e个边结点。而有向图中有n个顶点、e条边，则它的邻接表需要n个表头指针和e个边结点。（2）对于无向图，顶点vi的度是第i个链表的结点数。（3）对于有向图，顶点vi的出度是第i个链表的结点数，而求入度则必须遍历整个邻接表，即在所有链表中找邻接点域的值为i的边结点的个数。所以，对于那些需要经常查找顶点入边或入边邻接点的运算，可以为此专门建立一个逆邻接表，该表中每个顶点的单链表存储所有入边的信息。返回到本节目录3．建立邻接表的算法（1）以邻接表为存储结构定义图类型ALGRAPH。#defineNULL0/*NULL为空指针*/#defineMAXVEX100/*数组最大元素个数*/typedefcharVertexType[3];typedefstructedgenode{intadjvex;/*邻接点序号*/intvalue;/*边的权值*/structedgenode*next;/*下一条边的顶点*/}ArcNode;/*每个顶点建立的单链表中结点的类型*/返回到本节目录typedefstructvexnode{VertexTypedata;/*结点信息*/ArcNode*firstarc;/*指向第一条边结点*/}VHeadNode;/*单链表的头结点类型*/typedefstruct{intn,e;/*n为实际顶点数，e为实际边数*/VHeadNodeadjlist[MAXVEX];/*单链表头结点数组*/}AdjList;/*图的邻接表类型*/返回到本节目录(2)用邻接表为存储结构建立图的算法（如算法6.3所示）

算法6.3intCreateAdjList(AdjList*g){inti,b,t,w;ArcNode*p;printf("\n顶点数(n)，边数(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("\n序号为%d的顶点信息：",i);scanf("%s",g->adjlist[i].data);/*输入每个顶点的数据域*/g->adjlist[i].firstarc=NULL;/*邻接表的每个单链表头指针置空*/}返回到本节目录for(i=0;i<g->e;i++){printf("\n序号为边=>",i);printf("\n起点号

终点号

权值：");scanf("%d%d%d",&b,&t,&w);/*输入边的起始点、终止点和边的权值*/if(b<g->n&&t<g->n&&w>0)/*当输入数据正确时，生成新结点，插入邻接表的某个链表头部*/返回到本节目录{p=(ArcNode*)malloc(sizeof(ArcNode));p->value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;g->adjlist[b].firstarc=p;}else{printf("\n输入错误！");return(0);}}return(1);}返回到本节目录【例6.1】设计一个算法将有向图G的邻接矩阵存储结构结构转换成邻接表存储结构。解：给定邻接矩阵g，先创建邻接表G，给g.n个头结点置初值，扫描邻接矩阵g，对于不为0的权值g.edges[i][j]，创建一个结点，其value域值置为g.edges[i][j]，adjvex域置为j，将其插入到G->adjlist[i]为头结点的单链表的开头。最后设置G->n和G->e值。对应算法如算法6.5所示。返回到本节目录算法6.5AdjList*MatToList(AdjMatixg){inti,j;ArcNode*p;AdjList*G;G=(AdjList*)malloc(sizeof(AdjList));/*生成由G指向新的邻接表结点*/for(i=0;i<g.n;i++){G->adjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);/*复制图的数据域信息*/}返回到本节目录for(i=0;i<g.n;i++)for(j=0;j<=g.n-1;j++)if(g.edges[i][j]!=0){p=(ArcNode*)malloc((sizeof(ArcNode)));/*新建邻接表内链表结点*/p->value=g.edges[i][j];/*赋边的权值*/p->adjvex=j;/*赋值为该顶点的下一个邻接顶点*/p->next=G->adjlist[i].firstarc;/*p与下一个结点相连*/G->adjlist[i].firstarc=p;/*将p赋给邻接表头指针，为头插法*/}G->n=g.n;G->e=g.e;return(G);}返回到本节目录6.3图的遍历所谓图的遍历（traversinggraph）是指从图中的某一顶点出发，对图中的所有顶点访问一次，而且只访问一次。6.3.1深度优先搜索法6.3.2广度优先搜索法返回到总目录6.3.1深度优先搜索法1．深度优先搜索的方法：（1）首先从图中某个顶点发v出发，首先访问此顶点，将其标记为已访问过；（2）然后任选一个v的未被访问的邻接点w出发，继续进行深度优先搜索，（3）直到图中所有和v路径相通的顶点都被访问到；（4）若此时图中还有顶点未被访问到，则另选一个未被访问的顶点作为起始点。重复上面的做法，直至图中所有的顶点都被访问。返回到本节目录（a）无向G5

（b）图G5的邻接表图6-11图G5

及其邻接表返回到本节目录我们以图6-11（a）的无向图G5为例来说明其深度优先搜索的方法。假定我们以邻接表为存储结构。调用算法6.2，建成的邻接表如图6-11（b）所示(单链表中结点的插入方式为头插法)。则从顶点0出发，开始遍历（这里的0～7所说的是各顶点的编号）。图的深度优先搜索过程是一个递归过程，访问过程为：首先访问0（访问完，做上访问过标记）。查看0的链表，它的第一个未访问邻接点为2，于是访问2，并以2为出发点继续深度遍历。返回到本节目录查看2的链表，它的第一个未访问邻接点为6，于是访问6。从6号链表可知它第一个未被访问的邻接点为5，于是访问5。查看5的链表，它的邻接点2已经访问过，于是回到6号链表，搜索下一未被访问的邻接点。发现下一个邻接点2已经访问过且该链表不存在未被访问的邻接点，于是回到2号链表，搜索下一未被访问邻接点。发现2号也不存在未被访问邻接点，于是回到0号链表，搜索到下一个未被访问邻接点为1，于是访问1。返回到本节目录查看1的链表，它的第一个未被访问邻接点为4，于是访问4。查看4的链表，它的第一个未被访问的邻接点是7，于是访问7。查看7的链表，它的第一个邻接点已被访问，继续搜索下一未被访问邻接点是3，于是访问3。查看3链表已经不存在未被访问邻接点，于是回到4号表继续搜索，再回到1号链表，再回到0号链表，遍历最后完成。结果深度优先遍历序列是：0，2，6，5，1，4，7，3返回到本节目录2．深度优先搜索的算法算法6.6intvisited[MAXVEX];/*全局变量，访问数组*/voidDFS(AdjList*g,intvi){ArcNode*p;printf("%3d",vi);visited[vi]=1;p=g->adjlist[vi].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next;}}返回到本节目录6.3.2广度优先搜索法1．广度优先搜索的方法：假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。返回到本节目录我们还是以图6-11所示的无向图G5及其邻接表为例来说明其广度优先搜索的方法。初始准备，给标志数组visited[N]的每个元素赋初值0；假定从0号顶点出发，首先让0入队，做访问标记。广度优先搜索遍历过程如下：访问并删除队首结点0，然后遍历0号链表，让它的所有未做访问标记的邻接点（2，1）依次入队，并做访问标记。访问并删除队首结点2，然后遍历2号链表，让它的所有未做访问标记的邻接点（6，5）依次入队，并做访问标记。返回到本节目录访问并删除队首结点1，然后遍历1号链表，让它的所有未做访问标记的邻接点（4，3）依次入队，并做访问标记。访问并删除队首结点6，然后遍历6号链表。此时，链表中已无未做访问标记的顶点。访问并删除队首结点5，然后遍历5号链表。此时，链表中已无未做访问标记的顶点。访问并删除队首结点4，然后遍历4号链表。让它唯一未做访问标记的邻接点7入队，并做访问标记。访问并删除队首结点3，然后遍历3号链表。此时，链表中已无未做访问标记的顶点。访问并删除队首结点7，然后遍历7号链表。此时，链表中已无未做访问标记的顶点。此时，队列已空，遍历完成，最后的输出结果序列是：0，2，1，6，5，4，3，7。返回到本节目录2．广度优先搜索的算法算法6.7voidBFS(AdjList*g,intvi){inti,v,visited[MAXVEX];intqu[MAXVEX],front=0,rear=0;/*定义循环队列*/ArcNode*p;for(i=0;i<g->n;i++)/*辅助的访问数组赋初值*/visited[i]=0;printf("%5d",vi);/*输出起始访问顶点*/visited[vi]=1;

返回到本节目录rear=(rear+1)%MAXVEX;/*队尾指针后移*/qu[rear]=vi;/*将vi入队*/while(front!=rear)/*当队不空时*/{front=(front+1)%MAXVEX;v=qu[front];/*将队头元素出队，赋给顶点v*/p=g->adjlist[v].firstarc;/*将顶点v的下一条邻接边顶点指针赋给p*/while(p!=NULL){if(visited[p->adjvex]==0)/*若未访问过*/返回到本节目录{visited[p->adjvex]=1;/*访问数组该元素置1，已访问*/ printf("%5d",p->adjvex);/*输出该顶点*/rear=(rear+1)%MAXVEX;/*队尾指针后移*/qu[rear]=p->adjvex;/*将p所指的顶点入队*/}p=p->next;/*p指针后移*/}}}返回到本节目录6.4最小生成树在一个无向连通图G中，如果取它的全部顶点和一部分边构成一个子图，即：V(G′)=V(G)和

E（G′）

E（G）若边集E（G′）中的边既将图G中的所有顶点连通又不形成回路，则称子图G′是原图G的一棵生成树。6.4.1普里姆(Prim)算法6.4.2克鲁斯卡尔(Kruskal)算法返回到总目录6.4.1普里姆(Prim)算法1．基本思想假设G=（V，E）是一个具有n个顶点的连通图，T=（U，TE）是G的最小生成树，其中U是T的顶点集，TE是T的边集。U和TE初值均为空集。此算法的基本思想是：首先是从V中任取一个顶点（假定取v0），将它并入U中，即U={v0}，然后只要U是V的真子集，就从那些其中一个端点已在T中，另一个端点仍在T外的所有边中，找一条权值最小的边，假定为(vi,vj)，其中vi∈U，

vj∈(V-U)，并把该边(vi,vj)和顶点vj分别并入T的边集TE和顶点集U，如此不断重复，直到U=V，TE中含有n-1条边，T就是最后得到的最小生成树。返回到本节目录【例6.2】对于如图6-13所示的无向带权图，求利用普里姆算法从顶点a开始构造最小生成树的过程（可用表6-1的形式将每个步骤选择哪条边，U集合和V-U集合的变化过程表示出来），最后画出该图的最小生成树。图6-13带权无向图G7返回到本节目录解：用普里姆算法从顶点a开始构造最小生成树。设U为生成树顶点集合，V-U为未包含到生成树的图中顶点集合，构造最小生成树的生成过程如表6-2。表6-2图G7的最小生成树生成过程步骤当前V-U集合的内容当前U集合的内容生成树选择的边边的权值初始{a,b,c,d,e,f,g}{}{b,c,d,e,f,g}{a}1{b,c,d,e,f}{a,g}(a,g)32{b,c,d,f}{a,g,e}(g,e)23{b,c,d}{a,g,e,f}(e,f)14{b,c}{a,g,e,f,d}(e,d)35{c}{a,g,e,f,d,b}(g,b)66{}{a,g,e,f,d,b,c}(g,c)5返回到本节目录由表6-2得到图G7的最小生成树如图6-14所示。图6-14例6.2用普里姆算法构造的最小生成树返回到本节目录2．对应的普里姆算法算法6.8#defineMAXVEX100/*图中最大顶点个数*/#defineM32767/*32767代表无穷大*/voidPrim(intcost[][MAXVEX],intn,intv){intlowcost[MAXVEX],min;intclosest[MAXVEX],i,j,k;for(i=0;i<n;i++)/*给lowcost和closest赋初值*/{lowcost[i]=cost[v][i];closest[i]=v;}返回到本节目录for(i=1;i<n;i++)/*找出n-1个顶点*/{min=M;for(j=0;j<n;j++)/*在V-U中找出离U最近的顶点k*/if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("\n边(%d,%d)权为:%d",closest[k],k,min);lowcost[k]=0;/*标记k已经加入U*/for(j=0;j<n;j++)/*修改数组lowcost和closest*/if(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}返回到本节目录6.4.2克鲁斯卡尔(Kruskal)算法

1.基本思想克鲁斯卡尔（Kruskal）算法的思想是：假设G=（V，E）是一个具有n个顶点的连通网，T=（U，TE）是G的最小生成树。U的初值等于V，即即有G中的全部顶点。算法开始时，TE的初值为空集。将图G中的边按权值从小到大的顺序依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树T形成回路，则将其舍弃，如此进行下去，直到TE中包含n-1条边为止，此是的T即为最小生成树。返回到本节目录【例6.3】对于如图6-13所示的带权无向图G7，求利用普里姆算法从顶点a开始构造最小生成树的过程（可用表的形式写出生成树的集合变化情况和每次选择的边），并将生成树画出来。解：初始设每个顶点都是单独的一个生成树集合，按权值从小到大依次选择各边，只要两边的顶点分别在不同的生成树顶点集合里时，选择该边加入生成树边中。并将这两个顶点集合合并成一个集合。重复得到整个生成树。表6-4表示用克鲁斯卡尔算法生成最小生成树时生成树顶点集合的变化过程。返回到本节目录表6-4图G7用克鲁斯卡尔算法生成最小生成树的顶点集合变化过程步骤生成树中各顶点集合生成树的边生成树的权值初始状态{a},{b},{c},{d},{e},{f},{g}1{a},{b},{c},{d},{e,f},{g}(e,f)12{a},{b},{c},{d},{e,f,g}(e,g)23{a,e,f,g},{b},{c},{d}(a,g)34{a,e,f,g,d},{b},{c}(e,d)35{a,e,f,g,d,c},{b}(g,c)56{a,e,f,g,d,c,b}(g,b)6返回到本节目录由表6-4克鲁斯卡尔算法求最小生成树的过程如图6-16所示。图6-16例6.3题用克鲁斯卡尔算法构造的最小生成树返回到本节目录2．对应的克鲁斯卡尔算法（1）边的类型定义如下：#defineMAXVEX100typedefstruct{intu;/*边的起始顶点*/intv;/*边的终止顶点*/intw;/*边的权值*/}Edge;/*边的类型定义*/返回到本节目录（2）克鲁斯卡尔算法如算法6.9所示。算法6.9voidKruskal(EdgeE[],intn){inti,j,m1,m2,sn1,sn2,k;intvset[MAXVEX];for(i=0;i<n;i++)/*初始化辅助数组*/vset[i]=i;k=1;/*生成树中的第几条边*/j=0;/*E中边的下标,初值为0*/while(k<n)/*生成的边数小于n时循环*/{m1=E[j].u;m2=E[j].v;/*取一条边的两个顶点*/

返回到本节目录sn1=vset[m1];sn2=vset[m2];/*得到两条边的不同边号*/if(sn1!=sn2){printf("\n边(%d,%d)的权为:%d",m1,m2,E[j].w);k++;/*生成的边数加1*/for(i=0;i<n;i++)if(vset[i]==sn2)/*合并两个集合编号*/vset[i]=sn1;}j++;/*扫描下一条边*/}}返回到本节目录6.5拓扑排序AOV-网（ActivityOnVertex）：用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（ActivityOnVertexNetwork），简称为AOV-网。例如，一个计算机专业的学生必须学习一系列基本课程，其中有些课程是基础课，如高等数学，它独立于其他课程，而另一些课程必须在学完作为它的基础的选修课才能开始。如通常应该在学完“程序设计基础”和“离散数学”之后才开始学习“数据结构”。这种课程间的优先关系如图6-17表示。用顶点表示课程，弧表示先决条件，若课程Ci是课程Cj的先决条件，则有弧<Ci,Cj>存在。返回到总目录课程编号课程名称先修课程C1高等数学无C2程序设计基础无C3普通物理C1C4离散数学C1,C2C5C语言程序设计C2C6数据结构C2,C4,C5C7编译原理C5,C6C8计算机原理C3C9操作系统C6,C8表6-5计算机专业课必修示例返回到本节首页在AOV网中不应该存在回路，因为出现回路则表示某活动应以它自己的完成作为先决条件，这显然是不可能的。检测有向图是否存在回路的方法之一就是求图中顶点的一个满足下列性质的排列：即若有向图中有弧<i,j>存在，则在这个序列，i一定排在j之前，称有向图的这一操作为拓扑排序。图6-17表示课程之间优先关系的有向无环图返回到本节首页1．进行拓扑排序的方法（1）从有向图中选一个无前驱的顶点输出。（2）将此顶点和以它为起点的弧删除。（3）重复（1）、（2），直到不存在无前驱的顶点。（4）若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。返回到本节首页2．拓扑排序存储结构为了实现拓扑排序的算法，对于给定的有向图，采用邻接表作为存储结构，为每个顶点设立一个链表，每个链表有一个表头结点，这些表头结点构成一个数组，表头结点中增加一个存放顶点入度的域count。注意，其它结构体类型与前面介绍的邻接表定义的各类型相同，只将邻接表定义中的VHeadNode类型修改如下：typedefstructvexnode{VertexTypedata;/*结点信息*/intcount;/*该顶点的入度*/ArcNode*firstarc;/*指向第一条边结点*/}VHeadNode;/*单链表的头结点类型*/返回到本节首页3．拓扑排序的实现算法intCreateAdjList(AdjList*g){inti,b,t,w;ArcNode*p;printf("\n顶点数(n)，边数(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("序号为%d的顶点信息：",i);scanf("%s",g->adjlist[i].data);/*输入每个顶点的数据域*/g->adjlist[i].firstarc=NULL;/*邻接表的每个单链表头指针置空*/g->adjlist[i].count=0;/*邻接表的顶点入度域置为0*/}返回到本节首页for(i=0;i<g->e;i++){printf(“序号为%d的边=>",i);printf("起点号

终点号

权值：");scanf("%d%d%d",&b,&t,&w);/*输入边的起始点、终止点和边的权值*/if(b<g->n&&t<g->n&&w>0)/*当输入数据正确时，生成新结点，插入邻接表的某个链表头部*/{p=(ArcNode*)malloc(sizeof(ArcNode));p->value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;返回到本节首页 g->adjlist[b].firstarc=p;g->adjlist[t].count++;/*邻接表的顶点入度加1*/}else{printf("\n输入错误！");return(0);}}return(1);}返回到本节首页6.6AOE网与关键路径AOE网：在有向图中，用顶点表示事件，用弧表示活动，弧的权值表示活动所需要的时间。我们把用这种方法构造的有向无环图叫作边表示活动的网（ActivityOnEdgeNetwork）,简称AOE网。

1．AOE网中的基本概念（1）源点存在唯一的、入度为零的顶点，叫源点。（2）汇点存在唯一的、出度为零的顶点，叫汇点。返回到总目录（3）关键路径从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。（4）关键活动关键路径上的活动叫做关键活动。如图6-18所示的AOE-网。1为源点，表示整个工程可以开始，9为汇点，表示整个工程结束。返回到本节首页（1）事件vi的最早发生时间事件vi的最早发生时间用ve(i)表示。它是从源点到顶点vi的最长路径的长度。求ve(i)时可从源点开始，按拓扑顺序向汇点递推：ve(0)=0；ve(i)=max{ve(k)＋<k,i>上的权}（<k,i>∈T,1≤i≤n-1）其中，T为所有以i为头的弧<k,i>的集合。2．AOE中几个重要的参量定义返回到本节首页（2）事件vi的最迟发生时间事件vi的最迟发生时间用vl(i)表示，它是指在不推迟整个工程完成的前提下，该事件vi最迟必须发生的时间。在求出ve(i)的基础上，可从汇点开始，按逆拓扑顺序向源点递推，求出vl(i)：vl(n-1)=ve(n-1)；vl(i)=min{vl(k)＋(<i,k>上的权}（<i,k>∈S,0≤i≤n-2）其中，S为所有以i为尾的弧<i,k>的集合。返回到本节首页（3）活动ai的最早开始时间活动ai的最早开始时间用e(i)表示，它是该活动的起点所表示的事件最早发生时间。如果活动ai对应的弧为<j,k>，则e(i)等于从源点到顶点j的最长路径的长度，即：e(i)=ve(j)（4）活动ai的最晚开始时间活动ai的最晚开始时间用l(i)表示，如果活动ai对应的弧为<j,k>，则有：l(i)=vl(k)-<j,k>上的权返回到本节首页（5）活动ai的时间余量活动ai的时间余量可以用d(i)表示，ai的最晚开始时间与ai的最早开始时间之差d(i)=l(i)-e(i)显然，松弛时间（时间余量）为0的活动为关键活动。返回到本节首页3．求关键路径的基本步骤（1）对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)；（2）按逆拓扑序列求每个事件的最晚发生时间vl(i)；（3）求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)；（4)找出e(i)=l(i)的活动ai，即为关键活动。返回到本节首页4．求关键路径的过程（1）求AOE网中所有事件的最早发生时间ve(i)。（2）求AOE网中所有事件的最迟发生时间vl(i)。（3）求AOE网中所有活动的最早开始时间e(i)。（4）求AOE网中所有活动的最迟开始时间l(i)。（5）求AOE网中所有活动的时间余量d(i)。时间余量为0的活动即为关键路径。返回到本节首页【例6.4】对于图6-18所示的AOE网，求事件i的最早发生时间ve(i)和最迟发生时间vl(i)，求出活动ai的最早开始时间e(i)和最迟开始时间l(i)，并求出每个活动的时间余量d(i)，并确定该AOE网的关键路径。解：（1）求事件i的最早发生时间ve(i)如下：ve(1)=0ve(2)=6ve(3)=4ve(4)=5ve(5)=max{ve(2)+1,ve(3)+1}=7ve(6)=ve(4)+2=7ve(7)=ve(5)+9=16ve(8)=max{ve(5)+7,ve(6)+4}=14ve(9)=max{ve(7)+2,ve(8)+4}=18返回到本节首页（2）求事件i的最迟发生时间vl(i)如下：vl(9)=ve(9)=18vl(8)=vl(9)-4=14vl(7)=vl(9)-2=16vl(6)=vl(8)-4=10vl(5)=min{vl(7)-9,vl(8)-7}=7vl(4)=vl(6)-2=8vl(3)=vl(5)-1=6vl(2)=vl(5)-1=6vl(1)=min{vl(2)-6,vl(3)-4,vl(4)-5}=0（3）求所有活动的e(i)、l(i)和d(i)活动a1：

e(1)=ve(1)=0l(1)=vl(2)-6=0d(1)=0活动a2：

e(2)=ve(1)=0l(2)=vl(3)-3=3d(2)=3活动a3：

e(3)=ve(1)=0l(3)=vl(4)-5=3d(3)=3返回到本节首页活动a4：

e(4)=ve(2)=6l(4)=vl(5)-1=6d(4)=0活动a5：

e(5)=ve(3)=4l(5)=vl(5)-1=6d(5)=2活动a6：

e(6)=ve(4)=5l(6)=vl(8)-4=10d(6)=5活动a7：

e(7)=ve(5)=7l(7)=vl(7)-9=7d(7)=0活动a8：

e(8)=ve(5)=7l(8)=vl(8)-7=7d(8)=0活动a9：

e(9)=ve(6)=7l(9)=vl(8)-4=10d(9)=3活动a10：e(10)=ve(7)=16l(10)=vl(9)-2=16d(10)=0活动a11：e(11)=ve(8)=14l(11)=vl(9)-4=14d(11)=0当d(i)=0的路径为关键路径，所以图6-19所示的AOE网的关键路径为：a1，a4，a7，a8，a10，a11。因此关键路径为：（1，2，5，7，9）和（1，2，5，8，9）返回到本节首页6.7最短路径问题在网中，求点A到点B的所有路径中，边的权值之和最短的那一条路径。这条路径就称为两点之间的最短路径，并称路径上的第一个顶点为源点（Sourse），最后一个顶点为终点（Destination）。6.7.1求一个顶点到其他各顶点的最短路径6.7.2求每一对顶点之间的最短路径返回到总目录6.7.1求一个顶点到其他各顶点的最短路径

迪杰斯特拉（Dijkstra）提出了一个按长度递增的次序产生最短路径的算法。该算法的思路是：设有向图G=（V，E），其中，V={v0,v1,…,vn-1}，cost表示G的邻接矩阵（带权邻接矩阵）cost[i][j]是表示有向边<vi,vj>的权值。若不存在有向边<vi,vj>，则cost[i][j]的权值为无穷大（∞）。设置一维数组s[0..n-1]，用于标记已找到最短路径的顶点。设顶点v为源点，集合s的初态只包含顶点v。即：返回到本节目录以下用M表示∞，通常取大于最大权值的某个数值。设置一维数组s[0..n-1]，用于标记已找到最短路径的顶点。返回到本节目录数组dist记录从源点到其他各顶点当前的最短距离，其初值为dist[i]=cost[v][i]，从s之外的顶点集合V-S中选中一个顶点vu，使dist[u]的值最小。于是从源点到达vu只通过s中的顶点，把u加入集合s中调整dist中记录的从源点到V-S中每个顶点vj的距离：从原来的dist[j]和dist[u]+cost[u][j]中选择较小的值作为新的dist[j]。重复上述过程，直到s中包含其余各顶点的最短路径。返回到本节目录【例6.5】用迪杰斯特拉方法求图G8中从顶点0到达其它顶点的最短路径。解：使用迪杰斯特拉方法，令S={0}，数组dist初始值为源点0到其他各顶点的邻接边的权值，不邻接时对应的值为极大值M，如6-6所示的表的步骤0对应的行；选到某顶点的路径的最小值为10（0->2），利用顶点2修正从源点0到其他顶点的当前距离和当前路径，如顶点3的当前路径为M，而从源点1到2再到3的路径现在为50小于M，替换顶点1到顶点3的路径为(0,2,3)，并将顶点2并入集合S中。下次再取余下所有路径中的最小值30（0->4），利用顶点4修正从源点0到其它顶点的当前距离和当前路径，…，直到最后所有的顶点都并入到集合S中，求得从源点0到达其他各顶点的最短路径。返回到本节目录表6-6单源最短路径求解过程执行步骤顶点1顶点2顶点3顶点4顶点5经过VjS0M10(0,2)M30(0,4)100(0,5)-{0}170(0,2,1)60(0,2,3)30(0,4)100(0,5)2{0,2}270(0,2,1)50(0,4,3)90(0,4,5)4{0,2,4}370(0,2,1)60(0,4,3,5)3{0,2,4,3}470(0,2,1)5{0,2,4,3,5}51{0,2,4,3,5,1}返回到本节目录所以顶点0到达其它顶点的最短路径为：0->1：最短路径长度为70，路径为0->2->10->2：最短路径长度为10，路径为0->20->3：最短路径长度为50，路径为0->4->30->4：最短路径长度为30，路径为0->40->5：最短路径长度为60，路径为0->4->3->5返回到本节目录(1)迪杰斯特拉算法如算法6.11所示。算法6.11#defineMAXVEX100#defineM10000/*图的邻接矩阵中的极大值*/voidDijkstra(intcost[][MAXVEX],intn,intv){intdist[MAXVEX],path[MAXVEX];ints[MAXVEX];intmindis,i,j,u,pre;for(i=0;i<n;i++){dist[i]=cost[v][i];/*初始化距离*/s[i]=0;/*辅助数组s[]置初值为0*/if(cost[v][i]<M)path[i]=v;elsepath[i]=-1;}返回到本节目录s[v]=1;path[v]=0;for(i=0;i<n;i++){mindis=M;u=-1;for(j=0;j<n;j++)if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}if(u!=-1){s[u]=1;for(j=0;j<n;j++)if(s[j]==0)if(cost[u][j]<M&&dist[u]+cost[u][j]<dist[j]){dist[j]=dist[u]+cost[u][j];path[j]=u;}}}返回到本节目录printf("\nDijkstra算法求解如下：\n");for(i=0;i<n;i++){if(i!=v){printf("\n%d->%d:",v,i);if(s[i]==1){printf("路径长度为%2d,",dist[i]);pre=i;printf("路径逆序为：");while(pre!=v){printf("%d,",pre);pre=path[pre];}printf("%d\n",pre);}elseprintf("不存在路径\n");}}}返回到本节目录6.7.2求每一对顶点之间的最短路径1．弗洛伊德（Floyed）算法弗洛伊德（Floyed）