第8章图-图的基本概念

18.1图的基本概念第8章图8.2图的存储结构8.3图的遍历8.4生成树和最小生成树8.5最短路径8.6拓扑排序8.7AOE网与关键路径2图的示例V1V4V2V3V5V4V3V2V1结点之间的关系：多对多，任意两个结点之间都可能有关系存在边弧顶点3图的抽象数据类型ADTGraph{

数据对象：D={ai|1≤i≤n，n≥0，ai属ElemType类型}

数据关系：R={<ai,aj>|ai,aj∈D,1≤i≤n,1≤j≤n,其中每个元素可以有零个或多个直接前驱，可以有零个或多个直接后继}

基本操作P：

InitGraph(&g)//初始化图：构造一个空图g

ClearGraph(&g)//销毁图：释放图g占用的存储空间

DFS(g)//深度优先遍历图g

BFS(g)//广度优先遍历图g

…}ADTGraph48.1.1图的定义

图(Graph)G由两个集合V(Vertex)和E(Edge)组成,记为G=(V,E)，其中V是顶点的有限集合，E是连接V中两个不同顶点(顶点对)的边的有限集合。在图G中，如果代表边的顶点对是无序的，则称G为无向图，无向图中代表边的无序顶点对通常用圆括号括起来，用以表示一条无向边。如果表示边的顶点对是有序的，则称G为有向图，在有向图中代表边的顶点对通常用尖括号括起来。8.1图的基本概念51.端点和邻接点在一个无向图中,若存在一条边(vi,vj),则称vi和vj为此边的两个端点,并称它们互为邻接点。在一个有向图中,若存在一条边<vi,vj>,则称此边是顶点vi的一条出边,同时也是顶点vj的一条入边；称vi和vj分别为此边的起始端点(简称为起点)和终止端点(简称终点)；称vi和vj互为邻接点。8.1.2图的基本术语62.顶点的度、入度和出度在无向图中，顶点所具有的边的数目称为该顶点的度。在有向图中，以顶点vi为终点的入边的数目,称为该顶点的入度。以顶点vi为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。若一个图中有n个顶点和e条边，每个顶点的度为di(1≤i≤n)，则有：73.完全图若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。完全无向图包含有n(n-1)/2条边完全有向图包含有n(n-1)条边。84.稠密图、稀疏图当一个图接近完全图时，则称为稠密图。相反，当一个图含有较少的边数(即当e<<n(n-1))时，则称为稀疏图。

5.子图设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集,即V’V，且E’是E的子集，即E’E，则称G’是G的子图。例如图(b)是图(a)的子图，而图(c)不是图(a)的子图。96.路径和路径长度(略)

在一个图G=(V,E)中,从顶点vi到顶点vj的一条路径是一个顶点序列(vi,vi1,vi2,…,vim,vj)；若此图G是无向图,则边(vi,vi1),(vi1,vi2),…,(vim-1,vim),(vim,vj)属于E(G)；若此图是有向图,则<vi,vi1>,<vi1,vi2>,…,<vim-1,vim>,<vim,vj>属于E(G)。路径长度是指一条路径上经过的边的数目。若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。例如，(v0,v2,v1)就是一条简单路径，其长度为2。107.回路或环(略)若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。例如，(v0,v2,v1,v0)就是一条简单回路，其长度为3。118.连通、连通图和连通分量在无向图G中，若从顶点vi到顶点vj有路径，则称vi和vj是连通的。若图G中任意两个顶点都连通，则称G为连通图，否则称为非连通图。

无向图G中的极大连通子图称为G的连通分量。任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。CABDEFBDEFCA129.强连通图和强连通分量(略)在有向图G中，若从顶点vi到顶点vj有路径，则称从vi到vj是连通的。若图G中的任意两个顶点vi和vj都连通，即从vi到vj和从vj到vi都存在路径，则称图G是强连通图。

有向图G中的极大强连通子图称为G的强连通分量。1310.权和网图中每一条边都可以附有一个对应的数值，这种与边相关的数值称为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。边上带有权的图称为带权图，也称作网。v2v4v1v5v3v616211114336191865201531050v2v1v5v3v4v0202010301545无向网有向网14思考要连通具有n个顶点的无向图，至少需要（）条边？要连通具有n个顶点的有向图，至少需要（）条弧？n-1n158.2图的存储结构几种常用的存储结构邻接矩阵邻接表十字链表邻接多重表168.2.1邻接矩阵存储方法邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是具有n(n＞0)个顶点的图，顶点的顺序依次为(v0,v1,…,vn-1)，则G的邻接矩阵A是n阶方阵。其定义如下：

(1)如果G是无向图,则：

A[i][j]=1:若(vi,vj)∈E(G)0:其他

(2)如果G是有向图,则：

A[i][j]=1:若<vi,vj>∈E(G)0:其他

(3)如果G是带权无向图,则：

A[i][j]=wij:若vi≠vj且(vi,vj)∈E(G)∞:其他

(4)如果G是带权有向图,则：

A[i][j]=wij:若vi≠vj且<vi,vj>∈E(G)∞:其他171320413204A1＝0123401234A2＝0123401234对称不对称18（1）对于有n个顶点e条边的无向图，邻接矩阵表示时有多少个元素，多少个非0元素？（2）对于有n个顶点e条边的有向图，邻接矩阵表示时有多少个元素，多少个非0元素？（3）邻接矩阵中如何求顶点的度？思考19(1)图的邻接矩阵表示是唯一的。

(2)对于含有n个顶点的图，采用邻接矩阵存储时，无论是有向图还是无向图，也无论边的数目是多少，其存储空间均为O(n2)，所以邻接矩阵适合于存储边数较多的稠密图。

(3)无向图的邻接矩阵一定是一个对称矩阵。按照压缩存储的思想，只需存放上(或下)三角形阵的元素即可。

(4)对于无向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的度。

(5)对于有向图，邻接矩阵的第i行(或第i列)非零元素(或非∞元素)的个数正好是第i个顶点的出度(或入度)。

(6)用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。邻接矩阵的特点20#defineMAXV<最大顶点个数> typedefstruct{intno; /*顶点编号*/

InfoTypeinfo; /*顶点其他信息*/}VertexType; /*顶点类型*/typedefstruct /*图的定义*/{intedges[MAXV][MAXV]; /*邻接矩阵*/

intvexnum,arcnum; /*顶点数，边数*/

VertexTypevexs[MAXV]; /*存放顶点信息*/}MGraph;邻接矩阵的数据类型定义21顺序分配与链式分配相结合的存储方法。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)。每个单链表上附设一个表头结点。表结点和表头结点的结构如下：

表结点

表头结点adjvexnextarcinfodatafirstarc8.2.2邻接表存储方法221320413204datafirstarcadjvexnextarc表头结点表结点23（1）对于有n个顶点e条边的无向图，邻接表表示时有多少个表头结点，多少个表结点？（2）对于有n个顶点e条边的有向图，邻接表表示时有多少个表头结点，多少个表结点？（3）邻接表中如何求顶点的度？思考24(1)邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。

(2)对于有n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点。对于有n个顶点和e条边的有向图，其邻接表有n个表头结点和e个边结点。对于稀疏图，邻接表比邻接矩阵节省空间。

(3)对于无向图，邻接表的顶点vi对应的第i个链表的边结点数目正好是顶点vi的度。

(4)对于有向图，邻接表的顶点vi对应的第i个链表的边结点数目仅仅是vi的出度。其入度为邻接表中所有adjvex域值为i的边结点数目。邻接表的特点25typedefstructANode /*弧的结点结构类型*/{ intadjvex;/*该弧的终点位置*/

structANode*nextarc;/*指向下一条弧的指针*/

InfoTypeinfo; /*该弧的相关信息*/}ArcNode;typedefstructVnode/*邻接表头结点的类型*/{ Vertexdata; /*顶点信息*/

ArcNode*firstarc;/*指向第一条弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是邻接表类型*/typedefstruct{AdjListadjlist; /*邻接表*/

intn,e; /*图中顶点数n和边数e*/}ALGraph; /*图的类型*/邻接表存储结构的定义26已知无向图采用邻接表存储，写出删除边(i，j)的算法。voidDeletEdge(ALGraphg,inti,j){ p=g.adjlist[i].firstarc;pre=null;∥pre是前驱指针

while(p) if(p->adjvex==j) {if(pre==null)g.adjlist[i].firstarc=p->next; elsepre->next=p->next; free(p); }∥释放空间

else{pre=p;p=p->next;}∥沿链表继续查找

p=g.adjlist[j].firstarc;pre=null;∥删顶点j的边结点(j,i)

while(p)

if(p->adjvex==i)

{ if(pre==null)g.adjlist[j].firstarc=p->next;

elsepre->next=p->next;

free(p);

}∥释放空间

else{pre=p;p=p->next; }∥沿链表继续查找}∥DeletEdge27图的存储结构：逆邻接表若问题对入度更关心，则可以把线性链表改为：所有以头结点为弧头的弧组成的线性链表。此时该邻接表称为逆邻接表。v3v2v10v11v22v3∧011∧∧对于有向图，逆邻接表表示了顶点的入度28有向图的存储结构：十字链表有向图的十字链表可以同时表示一个顶点和其他顶点的所有关系：出度和入度十字链表(orthogonallist)把邻接表和逆邻接表结合起来29无向图的存储结构：邻接多重表问题：在无向图中，边是一种“对称”关系，因此在邻接表中，表示任一条边的结点都有两个，而且分别在两个不同的链表中。即：存储表示中信息有冗余，维护不容易。改进方法：用一个结点完整地表示一条边，在整个存储结构中，有且仅有一个存储单元来表示该边。v3v2v4v10v11v22v33v410002211333∧2∧∧∧30各种存储结构的适用类型邻接矩阵：有向图和无向图邻接表（逆邻接表）：有向图和无向图十字链表：有向图邻接多重表：无向图318.3.1图的遍历的概念图的遍历：从给定图中任意指定的顶点(称为初始点)出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次。如果给定图是连通的无向图或者是强连通的有向图，则遍历过程一次就能完成，并可按访问的先后顺序得到由该图所有顶点组成的一个序列。根据搜索方法的不同，图的遍历方法有两种：深度优先搜索法(DFS)广度优先搜索法(BFS)8.3图的遍历需要用一个数组visited[n]记录每个顶点的访问情况，以免同一个顶点被访问多次321、从图中某个初始顶点v出发，访问该顶点2、选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v连通的所有顶点都被访问过为止。显然，这个遍历过程是个递归过程。3、此时若图中尚有顶点未被访问，则另选图中下一个未被访问的顶点作起始点，访问该顶点，继续过程2。8.3.2深度优先遍历33abchdekfg812345670FFFFFFFFF012345678TTTTTTTTTachdkfebgachkfedbg访问标志:访问次序:achdkfe34图的深度优先遍历已知图G的邻接表如图所示，其从顶点V1出发的深度优先搜索序列为__________。V6∧V1143V2V3V4V5245352∧∧∧∧∧012345V6∧v1v2v3v6v5v435typedefstructANode /*弧的结点结构类型*/{ intadjvex;/*该弧的终点位置*/

structANode*nextarc;/*指向下一条弧的指针*/

InfoTypeinfo; /*该弧的相关信息*/}ArcNode;typedefstructVnode/*邻接表头结点的类型*/{ Vertexdata; /*顶点信息*/

ArcNode*firstarc;/*指向第一条弧*/}VNode;typedefVNodeAdjList[MAXV]; /*AdjList是邻接表类型*/typedefstruct{AdjListadjlist; /*邻接表*/

intn,e; /*图中顶点数n和边数e*/}ALGraph; /*图的类型*/邻接表存储结构的定义36voidDFS(ALGraph*G,intv){ArcNode*p;visited[v]=1; /*置已访问标记*/

printf("%d",v); /*输出被访问顶点的编号*/

p=G->adjlist[v].firstarc;

/*p指向顶点v的第一条弧的弧头结点*/

while(p!=NULL)

{if(visited[p->adjvex]==0)DFS(G,p->adjvex);

/*若p->adjvex顶点未访问,递归访问它*/

p=p->nextarc;

/*p指向顶点v的下一条弧的弧头结点*/

}}v是初始顶点编号，visited[]是一个全局数组，初始时所有元素均为0表示所有顶点尚未访问过37图的深度优先遍历intvisited[MAXNODE]//访问标志数组voidDFSTraverse(ALGraphG){for(i=0；i<G->n；i++)visited[i]=0；

for(i=0；i<G->n；i++)

if(visited[i]==0)DFS(G,i)；}//DFSTraverseDFS的调用次数即为连通分量的个数381、访问初始点vi2、接着访问vi的所有未被访问过的邻接点v1,v2,…,vt3、然后再按照v1,v2,…,vt的次序，访问每一个顶点的所有未被访问过的邻接点依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。8.3.3广度优先遍历39图的广度优先遍历v2v4v1v5v3v6v7v8广度优先搜索v1->v2->v3->v4->v5->v6->v7->v8v2v4v1v5v3v6v7v8回边40图的广度优先遍历已知图G的邻接表如图所示，其从顶点V1出发的广度优先搜索序列为____________。V6∧V1143V2V3V4V5245352∧∧∧∧∧012345V6∧v1v2v5v4v3v641voidBFS(ALGraph*G,intv){ArcNode*p;intw,i;intqueue[MAXV],front=0,rear=0; /*定义循环队列*/

intvisited[MAXV];/*定义存放结点的访问标志的数组*/

for(i=0;i<G->n;i++)visited[i]=0;/*访问标志数组初始化*/

printf("%2d",v);/*输出被访问顶点的编号*/

visited[v]=1;/*置已访问标记*/

rear=(rear+1)%MAXV;

queue[rear]=v; /*v进队*/

while(front!=rear) /*若队列不空时循环*/

{front=(front+1)%MAXV;

w=queue[front];/*出队并赋给w*/

p=G->adjlist[w].firstarc;/*找w的第一个邻接点*/

while(p!=NULL)

{ if(visited[p->adjvex]==0)

{ printf(“%2d”,p->adjvex); /*访问之*/

visited[p->adjvex]=1;

rear=(rear+1)%MAXV;/*该顶点进队*/

queue[rear]=p->adjvex;

}

p=p->nextarc;/*找下一个邻接顶点*/

}

}

printf("\n");}42思考题1对一个图进行遍历为什么可以得到不同的遍历序列？主要因素有：开始遍历的顶点不同；邻接点的顺序不同；43思考题2遍历图的过程实质上是______，breath-firstsearch和depth-firstsearch的不同之处在于______，反映在数据结构上的差别是______。（1）：查找顶点的邻接点的过程；（2）：访问顶点的顺序不同；（3）：队列和栈448.3.4非连通图的遍历（略）在对无向图进行遍历时：对于连通图，仅需调用遍历过程(DFS或BFS)一次，从图中任一顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需多次调用遍历过程，每次调用得到的顶点集连同相关的边就构成图的一个连通分量。调用两次DFS（分别从A、D出发），得到的顶点访问序列分别为：

A,B,CD,E,F

ACBDEFDEFBCA45确定连通分量的个数number=0;for(i=0；i<G->n;i++)

if(visited[i]==0)

{

++number;

DFS(G,i)；

}468.4.1生成树的概念

一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有构成一棵树的n-1条边。如果一个图有n个顶点和小于(n-1)条边，则是非连通图。如果它多于n-1条边，则一定有回路。生成树的构成：设G=(V,E)为连通图，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B，其中T是遍历图过程中走过的边的集合，B是剩余的边的集合。G‘=(V,T)是G的极小连通子图，即G'是G的一棵生成树。

8.4生成树和最小生成树47深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称为广度优先生成树。8.4.2无向图的连通分量和生成树生成树不唯一v3v2v1v4v3v2v1v4v3v2v4v1例8.1148最小生成树图的最小生成树：图的所有生成树中，边上的权值之和最小的树。实际问题：假设要在n个城市之间建立通信网络。则连通这n个城市只需要n-1条通信线路，如何在最节省经费的前提下建立这个通讯网？该问题等价于：在含有n个顶点的连通图的所有生成树中，选择一棵，使得各边权值之和最小。49假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树。由G构造最小生成树T的步骤如下：(1)初始化U={v}，以v到其他顶点的所有边为候选边；(2)重复以下步骤n-1次,使得其他n-1个顶点被加入到U中：①从候选边中挑选权值最小的边加入TE，设该边在V-U中的顶点是vk，将vk加入U中；②考察当前V-U中的所有顶点vj，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。8.4.3普里姆算法50Prim算法的实现设立辅助数组closedge，对每个顶点，存在一个相应分量，记录从U到vi的所有边中代价最小的边。数组closedge包括两个域：lowcost域存放该边上的权adjvex域存放该边依附的在U中的顶点显然：（其中表示赋予边的权）51Prim算法举例5

0

2

1

3

4

5

(a)

1

5

6

3

5

6

6

4

2

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

4

0

2

1

3

4

5

(d)

1

4

2

0

2

1

3

4

5

(e)

1

5

4

2

0

2

1

3

4

5

(f)

1

3

4

2

5

52Prim算法举例Adjvexlowcost

0

0

0

0

0{0,1,2,3,4,5}{}

closedge

12

3

4

5U

V－UAdjvexlowcost060105∞∞{0}{1,2,3,4,5}Adjvexlowcost250052624{0,2}{1,3,4,5}Adjvexlowcost25

052260{0,2,5}{1,3,4}Adjvexlowcost25

0

0260{0,2,3,5}{1,4}Adjvexlowcost

0

0

013

0{0,1,2,3,5}{4}i

53克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：(1)置U的初值等于V(即包含有G中的全部顶点)，TE的初值为空集(即图T中每一个顶点都构成一个分量)。(2)将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE；否则舍弃，直到TE中包含(n-1)条边为止。8.4.4克鲁斯卡尔算法54克鲁斯卡尔算法举例5

0

2

1

3

4

5

1

5

6

3

5

6

6

4

2

(e)

4

1

0

2

1

3

4

5

(a)

1

0

2

1

3

4

5

(b)

1

0

2

1

3

4

5

(c)

1

0

2

1

3

4

5

(d)

1

4

2

(e)

0

2

1

3

4

5

1

3

4

2

5

2

2

3

3

0

0

3

5

4

1

0

0

3

3

1

1

0

0

3

3

1

1

0

0

0

0

1

1

1

1

1

1

558.5.1路径的概念

在一个无权的图中，若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径,每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短(即经过的边数最少)的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。8.5最短路径（略）56

对于带权的图，考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度(权值之和)称为最短路径长度或者最短距离。57问题：给定一个带权有向图G与源点v，求从v到G中其他顶点的最短路径，并限定各边上的权值大于或等于0。8.5.2从一个顶点到其余各顶点的最短路径采用狄克斯特拉(Dijkstra)算法求解基本思想是：按最短路径长度递增的次序产生每条最短路径源点v1…v258源点v1…v2从源点到顶点v1的最短路径是所有最短路径中长度最短者在这条最短路径上，必定只包含一条权值最小的弧，由此，只要在所有从源点出发的弧中查找权值最小者即可长度次短者可能有两种情况：

1.它可能是从源点直接到该顶点的路径；

2.也可能是：从源点先到v1，再从v1到该顶点；其余依次类推设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合S；第二组为其余未确定最短路径的顶点集合U。59源点v到j的最小距离＝MIN(cvk+wkj,cvj)60S U dist[]123456{0} {1,2,3,4,5,6}{4,6,6,∞,∞,∞}{0,1}{2,3,4,5,6}{,

5,6,11,∞,∞}{0,1,2}{3,4,5,6} {,,6,11,9,∞}{0,1,2,3}{4,5,6} {,,,11,9,∞}{0,1,2,3,5}{4,6} {,,,10,,17}{0,1,2,3,5,4} {6} {,,,,,16}{0,1,2,3,5,4,6}{} {,,,,,}从源点到vj的最短路径长度61

问题：对于一个各边权值均大于零的有向图，对每一对顶点vi≠vj，求出vi与vj之间的最短路径和最短路径长度。

可以通过以每个顶点作为源点循环求出每对顶点之间的最短路径。弗洛伊德(Floyd)算法也可用于求两顶点之间最短路径。

8.5.3每对顶点之间的最短路径62

假设有向图G=(V,E)采用邻接矩阵cost存储，另外设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]表示当前顶点vi到顶点vj的最短路径长度。弗洛伊德算法的基本思想：递推产生一个矩阵序列A0,A1,…,Ak,…,An

其中Ak[i][j]表示从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度。初始时,有A-1[i][j]=cost[i][j]63

当求从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径长度时,要分两种情况考虑：一种情况是该路径不经过顶点编号为k+1的顶点,此时该路径长度与从顶点vi到顶点vj的路径上所经过的顶点编号不大于k的最短路径长度相同；另一种情况是从顶点vi到顶点vj的最短路径上经过编号为k+1的顶点。64Ak+1[i,j]=MIN(Ak[i,j],Ak[i,k+1]+Ak[k+1,j]65

该路径可分为两段:

(1)从顶点vi到顶点vk+1的最短路径;

(2)从顶点vk+1到顶点vj的最短路径。此时最短路径长度等于这两段路径长度之和。这两种情况中的较小值，就是所要求的从顶点vi到顶点vj的路径上所经过的顶点编号不大于k+1的最短路径。

弗洛伊德思想可用如下的表达式来描述：

A-1[i][j]=cost[i][j]Ak+1[i][j]=MIN{Ak[i][j],Ak[i][k+1]+Ak[k+1][j]

}(0≤k≤n-1)66设G=(V,E)是一个具有n个顶点的有向图，V中顶点序列v1,v2,…,vn称为一个拓扑序列，当且仅当该顶点序列满足下列条件：若<vi,vj>是图中的边(即从顶点vi到vj有一条路径)，则在序列中顶点vi必须排在顶点vj之前。在一个有向图中找一个拓扑序列的过程称为拓扑排序。

对有向图进行拓扑排序，可检查有向图中是否存在回路。

8.6拓扑排序67课程代号课程名称先修课程C1高等数学无C2程序设计无C3离散数学C1C4数据结构C2,C3C5编译原理C2,C4C6操作系统C4,C7C7计算机组成原理C2

例如，计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业。课程之间的先后关系可用有向图表示：拓扑序列1：C1-C3-C2-C4-C7-C6-C5拓扑序列2：C2-C7-C1-C3-C4-C5-C6按照任何一个拓扑序列都可以顺序地进行课程学习。68

拓扑排序方法如下：

(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它。

(2)从网中删去该顶点，并且删去从该顶点发出的全部有向边。

(3)重复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。若此时网不空，表明网中有环。

69abcghdfeabhcdgfe一个AOV-网的拓扑排序70为了实现拓扑排序的算法，对于给定的有向图，采用邻接表作为存储结构，为每个顶点设立一个链表，每个链表有一个表头结点，表头结点中增加一个存放顶点入度的域count。即将邻接表定义中的VNode类型修改如下：

typedefstruct /*表头结点类型*/

{Vertexdata; /*顶点信息*/

intcount; /*存放顶点入度*/

ArcNode*firstarc;/*指向第一条弧*/

}VNode;71voidTopSort(ALGragh*G){inti,j;intSt[MAXV],top=-1;/*栈St的指针为top*/

ArcNode*p;

for(i=0;i<G->n;i++)

G->adjlist[i].count=0;

for(i=0;i<G->n;i++)

{ p=G->adjlist[i].firstarc;

while(p!=NULL)

{ G->adjlist[p->adjvex].count++;

p=p->nextarc; }

}

for(i=0;i<G->n;i++)

if(G->adjlist[i].count==0) /*入度为0的顶点入栈*/

{top++;St[top]=i;}

while(top>-1)/*栈不为空时循环*/

{i=St[top];top--; /*出栈*/

printf("%d",i);p=G->adjlist[i].firstarc;

while(p!=NULL)

{j=p->adjvex;G->adjlist[j].count--;

if(G->adjlist[j].count==0)

{top++;St[top]=j;}

p=p->nextarc; /*找下一个相邻顶点*/

}

}}72用带权有向图描述工程的预计进度，估算工程完成的时间。AOE网(ActivityOnEdge)：以顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间，或者说活动e持续时间。8.7AOE网与关键路径（略）v1

表示工程的开始v2

表示a1活动的完成v5表示a4

和a5

的完成v8

表示a8

和a9

的完成v9

表示工程的结束事件解释每个事件给出某些活动完成的信号，即表示在它之前的活动已经完成，在它之后的活动可以开始v2v4v1v5v3v6v9v7v8a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4源点汇点73我们对AOE-网所关心的问题是:(1)完成整个工程至少需要多少时间(2)哪些活动是影响工程进度的关键完成工程的最小时间：从开始顶点到结束顶点的最长路径的长度。关键路径：从开始顶点到结束顶点的最长路径。事件vi能够发生的最早时间是从始点v1到顶点vi的最长路径的长，它决定了表示该事件的这个顶点发出去的所有边（弧）表示的活动的最早开始时间。我们用e(i)表示活动ai的最早开始时间，用l(i)表示活动ai的最迟开始时间。识别关键活动就是要找e(i)=l(i)的活动。

74e(i)和l(i)分别表示活动ai的最早和最迟开始时间，ve(j)和vl(j)分别表示事件vj的最早和最迟发生时间如果活动ai由弧<j,k>表示，其权记为c(<j,k>)，则活动开始时间的计算公式为：

e(i)=ve(j) l(i)=vl(k)-c(<j,k>)

事件发生时间的计算公式为：

(1)最早时间

ve(源点)=0

ve(j)=max{ve(i)+c(<i,j>)}<i,j>∈T，j=1,2,……,n

其中，T是所有以第j个顶点为头的弧的集合。

(2)最迟时间

vl(汇点)=ve(汇点)

vl(i)=min{vl(j)－c(<i,j>)}<i,j>∈S，i=n-1,……,1其中，S是所有以第i个顶点为尾的弧的集合。jkaii1ji2...ij2j1...75关键路径---求ve，向前推ve(1)=0ve(2)=6ve(3)=4ve(4)=5ve(5)=maxv2v4v1v5v3v6v9v7v8a1=6a2=4a3=5a4=1a5=