《数据结构课件5》由会员分享，可在线阅读，更多相关《数据结构课件5（98页珍藏版）》请在金锄头文库上搜索。
1、17.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性图的连通性7.5 7.5 拓扑排序和关键路径拓扑排序和关键路径7.6 7.6 最短路径问题最短路径问题2 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集V R构构成的数据结构。成的数据结构。 Graph = (V, VR )其中，VR| v,wV 且 P(v,w) 表示从 v 到 w 的一条弧，并称 v 为弧尾弧尾，w 为弧头弧头。 谓词 P(v,w) 定义了弧 的意义或信息。7.1 7.1 图的定义和术语图的定义和术语3 由于“弧”是有方
2、向的，因此称由顶点集和弧集构成的图为有向图有向图。EACBD例如例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 4若VR 必有VR, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边边。BCAFED由顶点集和边集构成的图称作无向图无向图。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) 5名词和术语名词和术语网、子图 完全图、稀疏图、稠密图邻接点、度、入度、出度路径、路径长度、简单路径、简单回路
3、连通图、连通分量、强连通图、强连通分量生成树、生成森林6ABECFAEFBBC设图G=(V,VR) 和图 G=(V,VR),且 VV, VRVR,则称 G 为 G 的子子图图。1597211132 弧或边带权的图分别称作有向网有向网或无向网无向网。7假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图; 含有 e=n(n-1) 条弧的有向图称作 有向完全图有向完全图; 若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。8 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，例如例如: :TD(B) = 3TD
4、(A) = 2 边(v,w) 和顶点v 和w 相关联相关联。 和顶点v相关联的边的数目边的数目定义为顶点v的度，度，记为记为TDTD（v v）。ACDFEB右侧图中9顶点的出度出度: : 以顶点v 为弧尾的弧的数目;ABECF对有向图来说对有向图来说，顶点的入度入度: : 以顶点v为弧头的弧的数目。顶点的度度( (TD)=)=出度出度( (OD)+)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3由于弧有方向性，则有入度入度和出度出度之分10设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j
5、)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如: :从A到F长度为 3 的路径A,B,C,F简单路径简单路径:指序列中顶点不重复出现的路径。简单回路简单回路:指序列中第一个顶点和最后一个顶点相同的路径。11若图G中任意两个顶点之间都有路径相通，则称此图为连通图连通图;若无向图为非连通图，则图中各个极大连通子图称作此图的连通连通分量分量。BACDFEBACDFE12 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对有向图，对有向图，否则，其各个强连通子图称作它的强连通分量强连通分量。13
6、 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。BACDFE14结构的建立和销毁结构的建立和销毁插入和删除顶点插入和删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基本操作基本操作15CreatGraph(&G, V, VR)； / 按定义(V, VR) 构造图DestroyGraph(&G)； / 销毁图结构的建立和销毁结构的建立和销毁16对顶点的访问操作对顶点的访问操作Lo
7、cateVex(G, u); / 若G中存在顶点u，则返回该顶点在 / 图中“位置位置” ；否则返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 对 v 赋值value。17对邻接点的操作对邻接点的操作FirstAdjVex(G, v); / 返回 v 的“第一个邻接点第一个邻接点” 。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相对于 w 的） “下一个邻下一个邻接接/ 点点”。若 w 是 v 的最后一个邻接点，则/ 返回“空”。18插入和删除顶点插入和删除顶点Inser
8、tVex(&G, v); /在图G中增添新顶点v。DeleteVex(&G, v); / 删除G中顶点v及其相关的弧。19插入和删除弧插入和删除弧InsertArc(&G, v, w); / 在G中增添弧，若G是无向的， /则还增添对称弧。DeleteArc(&G, v, w); /在G中删除弧，若G是无向的， /则还删除对称弧。20遍遍 历历DFSTraverse(G, v, Visit(); /从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数V
9、isit一次且仅一次。217.2 图的存储结构图的存储结构一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示22Aij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为23有向图的邻接矩阵有向图的邻接矩阵为非对称矩阵为非对称矩阵ABECD24#define MAXVERTEXNUM 20typedef enum DG,DN,UDG,UDN GraphKind;typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VR
10、Type是顶点关系类型。 / 对无权图，用1或0表示相邻否； / 对带权图，则为权值类型。 InfoType *info; / 该弧相关信息的指针 ArcCell,AdjMatrixMAXVERTEXNUMMAXVERTEXNUM;25typedef struct / 图的定义图的定义 VertexType vexsMAXVERTEXNUM; / 顶点信息 AdjMatrix arcs; / 弧的信息 int vexnum, arcnum; / 顶点数，弧数 GraphKind kind; / 图的种类标志 MGraph;26DBACFE二、图的邻接表二、图的邻接表 存储表示存储表示 A 1
11、4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 30 1 2 3 4 527有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECD可见，在有向图的邻接表中不易找到指向该顶点的弧28ABECD有向图的逆邻接表有向图的逆邻接表在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧01234A B C D E 30320 41 29typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *nextarc; / 指向下一条弧的指针 InfoType *info; / 该
12、弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构30typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAXVERTEXNUM; data firstarc顶点的结点结构顶点的结点结构31typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGraph;图的结构定义图的结构定义(邻接表)32三、有向图的十字链表存储表示三
13、、有向图的十字链表存储表示 ABCABC0 1 20 2 0 12 1 2 0 33弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点typedef struct ArcBox / 弧的结构表示弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; ArcBox;tailvexheadvexhlink tlinkinfo34顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出
14、弧第一条出弧typedef struct VexNode / 顶点的结构表示顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;datafirstinfirstout35typedef struct VexNode xlistMAXVERTEXNUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)36四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark; / 访问标记
15、 int ivex, jvex; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;边的结构表示边的结构表示37typedef struct / 邻接多重表邻接多重表 VexBox adjmulistMAXVERTEXNUM; int vexnum, edgenum; AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示3
16、87.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索39 从图中某个顶点顶点V0 出发，访问此顶点，然后依次从依次从V0的的各个未被访问的各个未被访问的邻接邻接点出发深度优先搜索遍历图点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历40SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V ;f
17、or (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。Vw1w3w241从上页的图解可见从上页的图解可见:1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历;解决的办法是:为每个顶点设立一个 “访问标志 visitedw”;2. 如何判别V的邻接点是否被访问？42如图如图如图如图G4G4：深到底深到底回退回退深到底深到底V1V2V4V8V5（V2V8均已访问）均已访问）深到底深到底V3V6V7回退回退访问访问V1V2V3V4V5V6V7V8 visited0.n-1visited0.n-1是一个辅助数组，记载顶点是否被访问过是一个辅助数组，记载顶点是否被访问
18、过是一个辅助数组，记载顶点是否被访问过是一个辅助数组，记载顶点是否被访问过visitedi=TRUE, 已访问过已访问过FALSE, 未访问过（初值）未访问过（初值）注意：注意：DFS序列不唯一，它与算法、图的存储结构及初始出发点有关。序列不唯一，它与算法、图的存储结构及初始出发点有关。43深度优先搜索递归过程深度优先搜索递归过程（采用邻接矩阵存储图）：采用邻接矩阵存储图）： void DFS(MGraph G,int i) coutG.vexi”; visitedi=TRUE; for(j=0;jG.vexnum;+j) if(!visitedj &G.arcsij.adj) DFS(G,j
19、); 44深度优先搜索递归过程深度优先搜索递归过程（采用邻接表存储图）：采用邻接表存储图）：void DFS(ALGraph G,int i) coutG.verticesi.data”; visitedi=TRUE; p=G.verticesi.firstarc; while(p) if(!visitedp-adjvex) DFS(G,p-adjvex); p= p-nextarc; 45 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先搜索遍历非连通图的深度优先搜索遍历46
20、void DFSTraverse(Graph G) / 对图对图 G 作深度优先遍历。作深度优先遍历。 for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w2, V-w8 的路径长度为1;V-w7, V-w3, V-w5 的路径长度为2;V-w6, V-w4 的路径长度为3。w1Vw2w7w6w3w8w5w449 从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按这些顶点被访问的先后次按这些顶点被访问的先后次序依次访问它们的邻接点序依次访问它们的邻接点，直
21、至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。50广度优先搜索（广度优先搜索（广度优先搜索（广度优先搜索（breadth-first-search)breadth-first-search)1)1) 首先访问指定首先访问指定首先访问指定首先访问指定顶点顶点顶点顶点v0v0，将将将将v0v0作为当前顶点作为当前顶点作为当前顶点作为当前顶点; ;2)2) 访问当前顶点的访问当前顶点的访问当前顶点的访问当前顶点的所有未访问过的邻接点所有未访问过的邻接点所有未访问过的邻接点所有未访问过的邻
22、接点，3)3) 并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点并依次将访问的这些邻接点作为当前顶点; ;4)4) 重复重复重复重复2 2），），），）， 直到直到直到直到所有顶点所有顶点所有顶点所有顶点被访问为止。被访问为止。被访问为止。被访问为止。对右图广度优先搜索，访问顶点序列为：对右图广度优先搜索，访问顶点序列为：对右图广度优先搜索，访问顶点序列为：对右图广度优先搜索，访问顶点序列为： V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8V8V1V2V3V4V5 V6V7注意：注意：B
23、FS序列不唯一，它与算法、图的存储结构及初始出发点有关。序列不唯一，它与算法、图的存储结构及初始出发点有关。51广度优先搜索算法（以邻接矩阵作存储结构）：广度优先搜索算法（以邻接矩阵作存储结构）：广度优先搜索算法（以邻接矩阵作存储结构）：广度优先搜索算法（以邻接矩阵作存储结构）：void BFSTraverse(MGraph G) for(i=0;iG.vexnum;+i)visitedi=FALSE; InitQueue(Q); for(i=0;iG.vexnum;+i) if(!visitedi) visitedi=TRUE;coutG.vexsi; EnQueue(Q,i); while
24、(!QueueEmpty(Q) DeQueue(Q,k); for(j=0;jG.vexnum;+j) if(!visitedj &G.arcskj.adj) coutG.vexsj; visitedj=TRUE; EnQueue(Q,j)； 52广度优先搜索算法（以邻接表作存储结构）：广度优先搜索算法（以邻接表作存储结构）：广度优先搜索算法（以邻接表作存储结构）：广度优先搜索算法（以邻接表作存储结构）：void BFSTraverse(ALGraph G) for(i=0;iG.vexnum;+i)visitedi=FALSE; InitQueue(Q); for(i=0;iG.vexnum
25、;+i) if(!visitedi) visitedi=TRUE;coutadjvex) coutadjvex.data; visitedp-adjvex=TRUE; EnQueue(Q,p-adjvex); p=p-nextarc; 537.4 7.4 图的连通性问题图的连通性问题 一、无向图的连通分量和生成树一、无向图的连通分量和生成树对连通图，仅需从图的任一顶点出发进对连通图，仅需从图的任一顶点出发进行行DFSDFS或或BFSBFS，可访问到图中所有顶点；可访问到图中所有顶点；对非连通图，则需从多个顶点出发进行对非连通图，则需从多个顶点出发进行搜索，每一次从一个新起点出发进行搜索搜索，每
26、一次从一个新起点出发进行搜索得到的顶点序列恰为其各个连通分量中顶得到的顶点序列恰为其各个连通分量中顶点集。点集。54若设以孩子兄弟链表作生成森林的存储结构，则下面若设以孩子兄弟链表作生成森林的存储结构，则下面若设以孩子兄弟链表作生成森林的存储结构，则下面若设以孩子兄弟链表作生成森林的存储结构，则下面算法生成非连通图的深度优先生成森林：算法生成非连通图的深度优先生成森林：算法生成非连通图的深度优先生成森林：算法生成非连通图的深度优先生成森林：void DFSForest(Graph G,CSTree &T)void DFSForest(Graph G,CSTree &T) T=NULL; T=N
27、ULL; for(i=0;iG.vexnum;+i)visitedi=FALSE; for(i=0;iG.vexnum;+i)visitedi=FALSE; for(i=0;iG.vexnum;+i) for(i=0;idata=GetVex(G,i); p=new CSNode;p-data=GetVex(G,i);/ /分配根结点分配根结点分配根结点分配根结点 p-firstchild=p-nextsibling=NULL; p-firstchild=p-nextsibling=NULL; if(!T)T=p if(!T)T=p;/;/是第一棵生成树的根是第一棵生成树的根是第一棵生成树的根
28、是第一棵生成树的根 else q-nextsibling=p else q-nextsibling=p;/;/是其它生成树的根是其它生成树的根是其它生成树的根是其它生成树的根 q=p q=p;/q;/q指示当前生成树的根指示当前生成树的根指示当前生成树的根指示当前生成树的根 DFSTree(G,i,p DFSTree(G,i,p); );/ /建立以建立以建立以建立以p p为根的生成树为根的生成树为根的生成树为根的生成树 55void DFSTree(Graph G,int v,CSTree &T)void DFSTree(Graph G,int v,CSTree &T) visitedv=T
29、RUE;first=TRUE; visitedv=TRUE;first=TRUE; for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w) for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w) if(!visitedw) if(!visitedw) p=new CSNode;p-data=GetVex(G,w); p=new CSNode;p-data=GetVex(G,w); p-firstchild=p-nextsibling=NULL; p-firstchild=p-nextsibling=NULL; if(first
30、) if(first)/ /w w是是是是v v的第一个未被访问的邻接点的第一个未被访问的邻接点的第一个未被访问的邻接点的第一个未被访问的邻接点 T-lchild=p;first=FALSE; T-lchild=p;first=FALSE;/ /是根的左孩子是根的左孩子是根的左孩子是根的左孩子 else q-nextsibling=p; else q-nextsibling=p;/ /是上一邻接点的右兄弟是上一邻接点的右兄弟是上一邻接点的右兄弟是上一邻接点的右兄弟 q=p; q=p; DFSTree(G,w,q); DFSTree(G,w,q); 56二、二、( (连通网的连通网的) )最小生
31、成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前如何在最节省经费的前提下建立提下建立这个通讯网通讯网？问题：问题：57 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法）58 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加在添加的顶点的顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之间之间必定存
32、在一条边，并且该边的权值在所有必定存在一条边，并且该边的权值在所有连通顶点连通顶点 v 和和 w 之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。普里姆算法的基本思想普里姆算法的基本思想:59abcdegf195141827168213127例如例如: :aedcbgf148531621所得生成树权值和 = 14+8+3+5+16+21 = 6760 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小
33、的边顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件:UV-U61 设置一个辅助数组，对当前设置一个辅助数组，对当前VU集集中的每个顶点，记录和顶点集中的每个顶点，记录和顶点集U中顶点中顶点相连接的代价最小的边：相连接的代价最小的边：struct VertexType adjvex; / U集中的顶点序号 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM;62abcdegf195141827168213127aedcbaaa19141814例如例如:e12ee8168d3dd7213c5 5 19 m m 14 m 1819 5 7
34、12 m m m 5 3 m m m m 7 3 8 21 m14 12 m 8 m 16 m m m 21 m 2718 m m m 16 2763void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=1; iG.vexnum; +i)
35、继续向生成树上添加顶点继续向生成树上添加顶点;64 k = minimum(closedge); / 求出加入生成树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; 65具体做法具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开
36、始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：66abcdegf195141827168213127aedcbgf148531621例如例如: :712181967算法描述算法描述:构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第第 i 条权值最小的边条权值最小的边(u,v); 若若(u,v)加入加
37、入ST后不使后不使ST中产生回路中产生回路， 则则 输出边输出边(u,v); 且且 k+;68普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法697.5 有向无环图及其应用有向无环图及其应用一、拓扑排序问题一、拓扑排序问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序拓扑排序。70何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图
38、中没有限定次序关系的顶点，则可以人为加上任意的次序关系。71例如：对于下列有向图BDAC可求得拓扑有序序列： A B C D 或 A C B D由此所得顶点的线性序列称之为拓扑有序序列72BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D73如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱没有前驱 的顶点，并输出之; 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所删去此顶点以及所 有以它为尾的弧有以它为尾的弧;74abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需
39、要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减175取入度为零的顶点v;m=0;while (v!=0) printf(v); +m; w=FirstAdj(v); while (w != 0) inDegreew-; w=nextAdj(v,w); 取下一个入度为零的顶点v;if mn printf(“图中有回路”);算算法法描描述述76 为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存“入度为零”的顶点。CountInDegree(G,indegree)
40、; /对各顶点求入度InitStack(S);for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度为零的顶点入栈77count=0; /对输出顶点计数while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w) -indegree(w); / 弧头顶点的入度减一 if (!indegreew) Push(S, w); /新产生的入度为零的顶点入栈 if (countG.vexnum) printf(“图中有回路”
41、)78二、关键路径问题二、关键路径问题: : 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。79整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。abcdefghk64521187244例如例如: :“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。源点汇点617480 如何求关键活动？如何求关键活动？ 什么是“关键活动关键活动” ？该活动的该活动的最早最早开始时间开始时间 = = 该活动的该活动的最迟最迟开始时间开始时间ijdut81
42、“事件(顶点)” 的 最早发生时间 ve(j)ve(j) = 从源点到顶点j的最长路径长度;“事件(顶点)” 的 最迟发生时间 vl(k) vl(k) = 从顶点k到汇点的最短路径长度;82 假设第 i 条弧为 则 对第 i 项活动言 “活动(弧)”的 最早开始时间 ee(i) ee(i) = ve(j); “活动(弧)”的 最迟开始时间 el(i) el(i) = vl(k) dut();83 事件发生时间的计算公式: ve(源点) = 0; ve(k) = Maxve(j) + dut() vl(汇点) = ve(汇点); vl(j) = Minvl(k) dut()84abcdefghk
43、645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列: a - d - f - c - b - e - h - g - k8506457715 14 181814161078660000645777 15 14141602366887 1086 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序; 而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序;因为 拓扑逆序序列即为拓扑有序序列的 逆序列逆序列，因此 应该在拓扑排序的过程中， 另设一个“栈栈”记下拓扑有序序列
44、。877.6 两点之间的两点之间的 最短路径问题最短路径问题 求从某个源点到其余各点的求从某个源点到其余各点的最短路径最短路径 每一对顶点之间的最短路径每一对顶点之间的最短路径 88 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想: 依依最短路径的长度最短路径的长度递增的次序求得递增的次序求得各条路径各条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有最短路径中长度最短者。v289 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短的最短路径最短路径的特点:路径长度最短的最短路径最短路径的特点: 它只可能
45、有两种情况:或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。90其余最短路径的特点：再下一条路径长度次短的最短路径最短路径的特点: 它可能有三种情况：或者是，直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。 它或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过已求得最短路径的顶点，再到达该顶点。91求最短路径的迪杰斯特拉算法：一般情况下，Distk = 或者 = + 设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点 k
46、 的最短路径。921）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）修改其它各顶点的Distk值。假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将 Distk 改为 Distu+G.arcsukV0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。93求每一对顶点之间的最短路径弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径94若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,
47、v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。951. 1. 熟悉图的各种存储结构及其构造算熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。存储结构和算法有密切联系。2. 2. 熟练掌握图的两种搜索路径的遍历：熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。先搜索的算法。 本章小结本章小结96 在学习中应注意图的遍历算法与在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的遍历算法之间的类似和差异。 3. 3. 应用图的遍历算法求解各种简应用图的遍历算法求解各种简单路径问题。单路径问题。4. 4. 理解教科书中讨论的各种图的理解教科书中讨论的各种图的算法。算法。97本章本章作业作业:7.14 7.15 7.16 7.22 7.23思考题思考题: : 7.5 7.7 7.9 7.10 7.11 7.1398
