《数据结构与算法》第七章图资料课件

1、第七章 图7.1 图的定义7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径71图的定义一、有向图和无向图顶点VertexV:顶点的有穷非空集合VR两个顶点之间的关系的集合若VR 则表示从v到w有一条弧Arc v称作弧尾或初始点，Tail w称作弧头或终端点, Head有向图无向图稀疏图稠密图网Network子图邻接点相关联顶点的度、入度、 出度图中边/弧的数目与顶点度的关系路径路径的长度连通图回路或环Cycle简单路径简单回路强连通图完全图有向完全图由顶点的集合和弧的集合构成的图称为有向图G1=(V1,A1)V1=v1,v2,v3,v4A1=

2、,若VR必有VR则用无序对(v,w)代替和称作边Edge由顶点的集合和边的集合构成的图称作无向图G2=(V2,E2)V2=v1,v2,v3,v4,v5E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5)二、完全图 Completed Graph完全图 有n*（n-1）/2条边的无向图有向完全图 有n*（n-1）条弧的有向图稀疏图 有很少条边或弧的图稠密图网Network 带权的图三、子图Subgraph若有两个图G =（V，E）,G1=（V1，E1）如果V1 V , E1 E,则称G1为G的子图子图四、度1.无向图G =（V，E）若边（v，v1）

3、E，则称顶点v和v1互为邻接点 边（v，v1）依附于顶点v和v1 或边（v，v1）与顶点v、v1相关联顶点v的度是和v相关联的边的数目,记作TD（v）2.有向图G =（V，A）弧v，v1A， 则称v邻接到v1 或v1邻接自v 弧v，v1和顶点v、v1相关联以顶点v为头的弧的条数称作v的入度,记作ID（v） 以顶点v为尾的弧的条数称作v的出度,记作OD（v） 顶点v的度TD（v）=ID（v）+OD（v）图中边/弧的数目与顶点度的关系(若图中有n个顶点，e条边/弧)五、路径1.无向图G=（V，E）中 从顶点v到v1的路径是一个顶点序列: v=Vi,0, Vi,1,Vi,m =v1 其中（Vi,j-

4、1，Vi,j）E， 1jm3.路径的长度是路径上边或弧的数目2.有向图G=（V，A） 从顶点v到v1的路径是一个有向顶点序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm4.第一个顶点与最后一个顶点相同的路径称为回路或环Cycle5.序列中顶点不重复出现的路径称为简单路径 除第一个和最后一个顶点外，其余顶点不重复出现的回路称为简单回路六、连通图 Connected Graph1.无向图 v到v1有路径，称v和v1是连通的 若图中任意两个顶点vi、vjV都是连通的 则称G是连通图2.若一个无向图中有n个顶点和少于n-1条边 则该图是非连通图 若它有多于n-1

5、条边，则一定有环3.有向图 对于每一对vi、vjV,从vi到vj和vj到vi 都存在路径,则称 G为强连通图七、图的ADTADT Graph数据对象V:V是具有相同特性的数据元素的集合，称为顶点。 数据关系R： R=VR VR=|v,wV且p(v,w), 表示从v到w的弧， 谓词P(v,w)定义了弧的意义或信息 基本操作P： CreateGraph(&G,V,VR); 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G. DestroyGraph(&G); 初始条件:图G存在. 操作结果:销毁图G。LocateVex(G,u); 初始条件：图G存在，u和G中顶点

6、有相同特征。 操作结果: 若G中存在顶点u，则返回该点在图中的位置,否则返回其它信息。GetVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果: 返回v的值PutVex(&G,v,value); 初始条件：图G存在，v是G中某个顶点。 操作结果: 对v赋值 value。FirstAdjVex(G,v); 初始条件：图G存在，v是G中某个顶点。 操作结果:返回v的第一个邻接顶点。 若顶点在G中没有邻接顶点，则返回“空”。NextAdjVex(G,v,w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果: 返回v的（相对于w的）下一个邻接顶点。 若w是v 的

7、最后一个邻接点则返回“空”。InsertVex(&G,v); 初始条件：图G存在，v和图中顶点有相同特征。 操作结果: 在图G中增添新顶点v。 DeleteVex(&G,v); 初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中增添弧。若G是无向的，则还增添对称弧DeleteArc(&G,v,w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在G中删除弧。若G是无向的，则还删除对称弧DFSTraverse(G,v,Visit(); 初始条件：图G存在，v是G某

8、个顶点，Visit是顶点的应用函数。 操作结果:从顶点v起深度优先遍历图G，并对每个顶点调用visit一次且 仅一次。一旦visit()失败，则操作失败。BFSTraverse(G,v,Visit(); 初始条件：图G存在，v是G某个顶点，visit是顶点的应用函数。 操作结果: 从顶点v起广度优先遍历图G， 并对每个顶点调用visit 一次且仅一次。 一旦visit()失败，则操作失败。ADT Graph7.2 图的存储结构在图中，无法用数据元素在存储区的物理位置表示元素之间的关系。一、数组表示法(邻接矩阵表示法) 用一个数组存储顶点的信息， 用另一个数组存储边或弧的信息-邻接矩阵0123v

9、1v2v3v401234南校区，105号北一区，83号北二区，56号东一区，甲23东二区，5号15105301220321041.图的数组存储表示/ _ _ _ _ _ _图的数组（邻接矩阵）存储表示 _ _ _ _ _ _ _#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enum DG,DN,UDG,UDNGraphKind; /有向图，有向网，无向图，无向网typedef struct ArcCellVRType adj; /VRType是顶点关系类型.对无权图,用1或0 /表示相邻否；对带权图

10、，则为权值类型。 InfoType *Info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; / 顶点向量 AdjMatrix arcs; / 邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志MGraph;Mgraph G1; G1.vexnum=4G1. arcnum=4 G1.kind=DG 0123v1v2v3v4G1.vexsG1.arcs01.adj=1

11、G1.arcs2图的构造方法Status CreateGraph( MGraph &G)/ 采用数组（邻接矩阵）表示法，构造图G scanf(&G.kind); switch (G.kind) case DG: return CreateDG(G); / 构造有向图G case DN: nretur CreateDN(G); / 构造有向网G case UDG: return CreateUDG(G); / 构造无向图G case UDN: return CreateUDN(G); / 构造无向网G default : return ERROR; / CreateGraph Status Cr

12、eateUDN(MGraph &G)/采用数组（邻接矩阵）表示法，构造无向网Gscanf(&G.vexnum, &G.arcnum, &IncInfo); / IncInfo 为0则各弧不含其它信息for (i=0; iG.vexnum; +i ) scanf (&G.vexsi); / 构造顶点向量for (i=0; iG.vexnum; +i ) / 初始化邻接矩阵 for (j=0; jG.vexnum; +j ) G.arcsij=INFINITY, NULL; /adj,infofor (k=0; kG.arcnum; +k ) / 构造邻接矩阵 scanf (&v1, &v2, &

13、w); / 输入一条边依附的顶点及权值 i =LocateVex(G, v1 ); j = LocateVex (G, v2 ); / 确定v1和v2在G中位置 G.arcij.adj = w; / 弧的权值 if (IncInfo) Input(* G.); / 若弧含有相关信息,则输入 G.arcsji =G.arcsij; / 置的对称弧 return OK; / CreateUDN二、邻接表Adjacency List方法：对每个顶点建立一个单向链表 链接与vi有边相连的顶点（无向图） 或从vi出发到达的顶点（有向图） datafirstarc指向该点出发到达的第

14、一条弧adjvex nextarc info每个顶点对应一个头结点每条边/弧对应一个结点到达顶点 下一条边/弧 边的信息无向图边结点有向图/- - - - - - - 图的邻接表存储表示 - - - - - - - #define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode * nextarc; / 指向下一条弧的指针 InfoType * info; / 该弧相关信息的指针ArcNode ;typedef struct VNode VertexType data; / 顶点信

15、息 ArcNode * firstarc; / 指向第一条依附顶点的弧的指针VNode, AdjListMAX_VERTEX_NUM ;typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 int kind; / 图的种类标志 ALGraph;ALGraph G1;G1.kind=DG;G1.vexnum=4G1.arcnum=4G1.verticesdatafirstarcadjvex info nextarc三、十字链表 Orthogonal List方法：图中的每个顶点用一个结点表示：图中的每一弧也用一个结点表

16、示：data firstinfirstouttailvex headvex hlink tlink info# define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex ; / 该弧的尾和头顶点的位置 struct ArcBox *hlink, *tlink; /分别为弧头相同和弧尾相同的弧的链域 Info type *info; / 该弧相关信息的指针ArcBox;typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分别指向该顶

17、点第一条入弧和出弧 VexNode ;typedef struct VexNode xlist MAX_VERTEX_NUM ; / 表头向量 int vexnum, arcnum; / 有向图的当前顶点数和弧数 OLGraph ;Status CreateDG(OLGraph &G) /采用十字链表存储表示， /构造有向图G, IncInfo为0则各弧不含其它信息 scanf(&G.vexnum, &G.arcnum, &IncInfo); for(i=0; iG.vexnum; +i ) / 构造表头向量 scanf(&G.xlisti.data); / 输入顶点值 G.xlisti.fi

18、rstin = NULL; G.xlisti.firstout = NULL; / 初始化指针 for(k=0; kinfo); /若弧含有相关信息，则输入 / CreateDG四、邻接多重表 Adjancency Multilist 顶点和边分别用一个结点表示 边：mark ivex ilink jvex jlink info该边是否搜索过顶点i在图中的位置(编号)下一条与i有关的边有关边的信息data firstedge顶点：242342# define MAX_VERTEX_NUM 20typedef enum unvisited, visitedVisitIf ;typedef str

19、uct EBox VisitIf mark; / 访问标记 int ivex, jvex; / 该边依附的两个顶点的位置0 struct EBox * ilink, * jlink; /分别指向依附这两个顶点的下一条边 InfoType * info; / 该边信息指针 EBox;typedef struct VexBox VertexType data; EBox * firstedge ; / 指向第一条依附该顶点的边 VexBox;typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum, edgenum; / 无向图的当前顶

20、点数和边数AMLGraph ;73图的遍历Traversing Graph图的遍历： 从图中某个顶点出发访问遍图中每个顶点， 且图中每个顶点仅被访问一次。遍历过程中每个顶点可能被访问多次， 因此，每个顶点被访问后需作一个标记 一般用一个数组标记某个结点是否被访问遍历方法：深度优先搜索、广度优先搜索一、深度优先收索Depth-First-Search(DFS)方法： 从图中某个顶点出发（设为v1），访问v1， 从v1出发,选择一个未被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未被访问的邻接点, 若图中仍有未

21、被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。v1v2v3v4v5v6v7 从v1出发,选择一个未被访问的邻接点vk,访问vk， 从vk出发，选择一个未被访问的邻接点, 若vk的所有邻接顶点都被访问过了， 回到vk-1,再选择的一个未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。v8Boolean visitedMAX; / 访问标志数组Status (* VisitFunc)(int v); / 函数指针变量void DFSTraverse(Graph G, Status(* Visit)(in

22、t v) / 对图G作深度优先遍历VisitFunc = Visit; /使用全局变量VisitFunc，使DFS不必设函数指针参数 for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 访问标志数组初始化 for(v=0; v0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /对v的尚未访问的邻接顶点w递归调用DFS printf(v); /起什么作用ABCDEFHGK123456789搜索回退ABCDEFHGK12345679二、广度优先收索Breadth-First-Search(BFS)方法： 从图中某个顶

23、点出发（设为vi），访问vi， 从vi出发，依次访问vi的所有未被访问的邻接点， 再从这些邻接点出发， 依次访问它们的所有未被访问的邻接点, 若图中仍有未被访问的顶点， 从中选择一个作为起点，重复上述过程 直到所有顶点均被访问过为止。void BFSTraverse(Graph G,Status(* Visit)(int v) / 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 for(v=0; vG.vexnum; +v ) visitedv = FALSE; InitQueue(Q); / 置空的辅助队列Q for (v=0; v0;w=NextAdjVex(G,u

24、,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未访问的邻接顶点w入队列Q /while / if / BFSTraverse搜索ABCDEFHGK123456789ABCDEFHGK12345678974图的连通性问题一、无向图的连通分量和生成树1.连通分量 无向图的极大连通子图。即:子图中不能再增加一个顶点,已有顶点的边均包含在内。 无向图的连通分量的产生-多次调用DFS2.生成树 一个连通图的生成树是一个极小连通子图,且含有图中全部顶点无向图连通分量连通图生成树3.无向图的生成树 对一个连通图G，从图中任意一

25、个顶点出发遍历图时，把E分为E1和E2，E1为遍历过程中经过的边的集合，E2为剩余边的集合，则E1与V构成G的极小连通图，即连通图的一棵生成树 若遍历为DFS，则称为深度优先生成树 若遍历为BFS，则称为广度优先生成树v1v2v3v4v5v6v7v8深度优先生成树v1v2v3v4v5v6v7v8广度优先生成树v1v2v3v4v5v6v7v8对于非连通图，每个连通分量中的顶点集合,加上遍历时经过的边，构成了非连通图的生成森林。生成森林4.无向非连通图的深度优先生成森林void DFSForest(Graph G,CSTree &T) /建立无向图的深度优先生成森林的(最左)孩子(右)兄弟链表 T

26、=NULL; for(v=0; vG.vexnum; +v) visitedv=FALSE; /顶点遍历初始化 for(v=0; vnextsibling=p; /是其它生成树的根(前一棵的根的兄弟） q=p; /q指示当前生成树的根 DFSTree(G,v,p); /建立以p为根的生成树 /DFSForestvoid DFSTree(Graph G, int v, CSTree &T) / 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树。 visitedv=TRUE; first =TRUE; for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w

27、) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode); / 分配孩子结点 *p=GetVex(G,w), NULL, NULL ; if(first) / w是v的第一个未被访问的邻接顶点 T-firstchild=p; first= FALSE; /是根的第一个孩子结点 else / w是v的其它未被访问的邻接顶点 q-nextsibling = p; /是上一邻接顶点的右兄弟结点 q = p; DFSTree(G,w,q);/从第w个顶点出发深度优先遍历图G,建立子生成树q / if/ DFSTree二、最小生成树Mininum Cost Span

28、ning Tree问题： 设有n个城市，两个城市之间都可以有一条路线，如何从最多n(n-1)/2条边中选择代价和最小的n-1条边(要包含所有顶点),就是连通图的最小代价生成树问题，简称最小生成树。 1.普里姆算法Prim 设N=（V，E）为连通网 用TE表示N上最小生成树边的集合 (1)从V中选一顶点u0加入U，TE= (2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2)，直到U=V为止,则（V，TE）为N的最小生成树 UV-Uv4v6v1v2v3v51555666342v1v31v1v31v64v42v25v53v1v31v64

29、v42v1v31v64v25v42v1v31v642MST性质(Prime算法正确性证明）设N=(V,E)是一个连通图, U是V的一个非空子集若(u,v)是一个具有最小代价的边,uU，vV-U则必存在一棵包含边(u ,v)的最小生成树uvuvUV-U证明： 假设网N的任何一棵最小生成树都不包含(u ,v) 设T是N上的一棵最小生成树，把(u ,v)加入到T中 则T中必存在一条包含(u ,v)的回路 同时,T中必存在另一条边(u,v)， 其中uU vV-U 并且u和u ,v和v之间均存在路径相通 删去边(u,v)，则可削去回路， 得到另一棵生成树T 显然,T的代价不高于T,且包含边(u ,v),

30、矛盾。设N=（V，E）为连通网用TE表示N上最小生成树边的集合(1)从V中选一顶点u0加入U，TE=(2)对所有uU，vV-U，（u，v）E,找一条代价最小的边（u0，v0）加入TE,并把v0加入U (3)重复(2),直到U=V为止,则（V,TE）为N的最小生成树 图-邻接矩阵最小的边（u0，v0）（ u0U，v0V-U）用矩阵closedge表示struct VertexType adjvex; /最短的边对应u中的顶点 VRType lowcost;/记录u中顶点到顶点j的最短的边 closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G

31、,VertexType u)k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 辅助数组初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = ufor(i=1; iG.vexnum;+i) / 选择其余G.vexnum-1个顶点 k =minimum(closedge); /求出T的下一个结点:第k顶点 printf(closedgek.adjvex,G.vexsk); /输出生成树的边 closedgek.lowcost = 0;

32、 /第k顶点并入U集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree1234UV-UkadjvexlowcostA2AA6A4AB,C,D,EadjvexlowcostA, adjvexlowcostadjvexlowcostadjvexlowcost3.克鲁斯卡尔算法 设连通图N=（V，E） (1)构造非连通图T=(V,),图中每个顶点自成一个连通分量 (2)在E中选择代价最小的边（u，v），并删去该边。若(u,v)落在T中不同的

33、连通分量上,则将此边加入T中 (3)重复(2），直到T中只有一个连通分量为止v1v2v3v4v5v6v4v6v1v2v3v515556663421v1v2v3v4v5v612453v1v2v3v4v5v612v1v2v3v4v5v6123v1v2v3v4v5v614236.5有向无环图及其应用一、DAG图 -Directed Acycline Graph 一个无环的有向图称为有向无环图二、拓扑排序 Topological Sort1AOV网 Activity On Vertex Network 用顶点表示活动， 用弧表示活动之间的优先关系的有向图 称为顶点表示活动的网，简称AOV网。 在网中,

34、若顶点i到顶点j有一条路径,则i为前驱, j为后继。若A，则vi为vj的直接前驱，vj为vi直接后继在AOV网中不能出现环，判定网中是否出现环的办法是拓扑排序。若所有的顶点都在拓扑有序序列中，则AOV网中无环，否则有环。C语言程序设计数据结构与算法面向对象程序设计计算机网络原理信息科学导论电路原理大学物理数字逻辑电路实验 组成原理实验操作系统汇编语言程序设计高等数学1离散数学数据库原理线性代数基础物理实验B高等数学2高等数学3C程序设计实验数据结构实验电路原理实验概率与数理统计数字逻辑电路计算机组成原理网络原理实验操作系统实验 面向对象实验2拓扑次序 设AOV网中有n个顶点V1，V2，Vn，

35、将顶点排成这样一个线性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一个排列 且若V ij，V ikA，则jk对AOV网给出拓扑次序的过程称为拓扑排序3拓扑排序算法(1)在网中选一个没有前驱的顶点且输出它(2)从图中删去该顶点及所有以它为尾的弧(3)重复(1)(2)直到所有顶点被输出 或图中不存在无前驱的顶点为止。采用邻接表作存储结构。用一个数组indegree存放顶点的入度。用一个栈存放入度为0的顶点Status TopologicalSort( ALGraph G) /有向图G采用邻接表存储结构。 /若G无回路,则输出G的顶点的一个拓扑序列并返回OK, /否则ERROR F

36、indInDegree(G,indegree); /对各顶点求入度indegree InitStack(S); / 建零入度顶点栈S for(i=0; inextarc) k = p-adjvex; /对i 号顶点的每个邻接的入度减1 if(!(- -indegreek)Push(S, k); /若入度减为0，则入栈 / for DestroyStack(S); if(countG.vexnum) return ERROR; /该有向图有回路 else return OK;/ TopologicalSort。还可以利用深度优先遍历过程进行拓扑排序，按退出DFS的逆序为拓扑次序v1v2v3v4v

37、5v6123456拓扑次序为：v6、v1、v4、v3、v5、v24.关键路径 AOE网Activity On Edge 顶点-事件 边-活动 权-活动持续的时间 用AOE网估计工程的完工时间Vi表示在此之前的活动已完成，在此之后的活动可以开始a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=412345买面粉3买鸡蛋3买白菜4买熟食667剁馅5切2和面2煮鸡蛋1包饺子4最短要多久才能包好饺子,开始聚餐?在一般情况下,AOE网中只有一个入度为0的顶点,称为源点只有一个出度为0的顶点，称为汇（聚）点？完成整个工程至少需要多少时间 -从源点到汇点的最长路径？哪

38、些活动是影响工程进度的关键路径长度最长的路径叫做关键路径 Critical Path从源点到Vi的最长路径叫做事件的最早发生时间,也就是所有以Vi为尾的弧所表示活动的最早开始时间 令e(i)表示ai的最早开始时间 l(i)表示ai的最迟开始时间 l(i)-e(i)为时间余量关键路径上的所有活动有：l(i)=e(i) 把所有e(i)=l(i)的活动叫做关键活动。设ai由弧表示 ve(j)表示事件j的最早发生时间 vl(j)表示事件j的最迟发生时间 ai的持续时间为dut() 则：e(i)=ve(j) l(i)=vl(k)-dut()a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7

39、a9=4a10=2a11=4最早开始时间:前驱活动都按期完成情况下的开始时间最迟开始时间:保证所有活动都能按期完成情况下最晚开始时间关键路径上的所有活动最早=最迟计算的方法：（1）ve(0)=0（2）按拓扑顺序计算： 其中T是所有以第j个顶点为头的弧的集合i1i2i3j（3）vl(n-1)=ve(n-1)（4）按逆拓扑顺序计算： 其中S是所有以第i个顶点为尾的弧的集合 j1j2j3i（5）根据各顶点的ve和vl的值 计算每条弧s的e(s)和l(s)a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4ve(3)=5ve(4)=7ve(7)=14ve(8)=

40、18vl(8)=18vl(7)=14vl(6)=16vl(4)=7ve(0)=0vl(1)=6vl(2)=6vl(0)=0ve(5)=7ve(6)=16vl(5)=10vl(3)=8ve(2)=4ve(1)=6Status TopologicalOrder(ALGraph G, Stack &T) FindInDegree(G, indegree); /对各顶点求入度indegree InitStack(S);/建零入度顶点栈S for(i=0; inextarc) k = p-adjvex; / 对j号顶点的每个邻接点的入度减1 if(-indegreek=0)Push(S, k); /若入

41、度减为0，则入栈 if(vej+*(p-info)vek)vek=vej+*(p-info); / *(p-info)= dut() / while DestroyStack(S); if(countnextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / forfor(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; tag=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag

42、); / 输出关键活动 / CriticalPath76最短路径 用顶点表示城市， 用边表示城市之间的交通状况 用边上的权表示城市之间的耗费（距离、时间、各种费用等）一、从一点到另一点，经过的结点最少二、从某个源点到其余各个顶点的最短路径 给定带权的有向图G和源点v， 求从v到G中其余各点的最短路径方法：按路径长度递增序产生最短路径 -迪杰斯特拉Dijksta方法v0v560v1v2v3v410030101050520v0v5v1v2v3v430101020存储结构用带权的邻接矩阵arcs表示带权有向图arcsij= A 上的权值 A算法(1)设S为已找到从v出发的最短路径的终点集合, 初值S

43、= Di表示从v到Vi的最短路径的长度 若A,Di为从v到Vi上的权,否则为 即：Di=arcsLocateVex(G,v),i, ViV(2)选择Vj，使得 Dj=minDi| ViV-S 并修改S: S=Sj Vj就是一条从v出发的最短路径的顶点(3)修改从v出发到集合V-S上任一点Vk可到达的最短路径 即如果 Dj+arcsjkDk 则： Dk=Dj+arcsjk(如果S为已求得最短路径的终点集合,则下一条最短路径或者是弧, 或者是从v到Vk加上弧,其中 VkS）(4)重复(2)(3)共n-1次,求得从v到图中其余各顶点的最短路径终点从V0到各终点D值和最短路径的求解过程V1V2V3V4VjV5i=1V210(V0 ,V2)30(V0 ,V4)100(V0 ,V5)V0 ,V2S30(V0 ,V4)100(V0 ,V5)60(V0 ,V2,V3)V0 ,V2,V4V4i=2i=550(V0 ,V4 ,V3)90(V0 ,V4 ,V5)V3i=3V0,