《图及其应用课件》由会员分享，可在线阅读，更多相关《图及其应用课件（118页珍藏版）》请在金锄头文库上搜索。
1、17.1 抽象数据类型图的定义抽象数据类型图的定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.6 最短路径问题最短路径问题7.5 拓扑排序拓扑排序 、关键路径、关键路径21.熟悉图的各种熟悉图的各种存储结构存储结构及其及其构造算法构造算法，了解实际问题的求解效率，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。与采用何种存储结构和算法有密切联系。2. 熟练掌握图的两种搜索路径的熟练掌握图的两种搜索路径的遍历遍历：深度优先搜索和广度优先搜：深度优先搜索和广度优先搜索的算法。索的算法。3. 图的算法应用。图的算法应用。学习提要学习提要3图图(G
2、raph)：图：图G是由两个集合是由两个集合V(G)和和E(G)组成的组成的,记为记为G=(V,E)。 其中：其中：V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)是边的有限集合，是边的有限集合，边是顶点的无序对或有序对。边是顶点的无序对或有序对。有向图有向图：有向图：有向图G是由两个集合是由两个集合V(G)和和E(G)组成。组成。 其中：其中：V(G)是顶点的非空有限集是顶点的非空有限集E(G)是有向边（也称弧）是有向边（也称弧）的有限集合，弧是顶点的有序对，记为的有限集合，弧是顶点的有序对，记为，v,w是顶点，是顶点，v为为弧尾弧尾，w为为弧头弧头。无向图无向图：无向图：无向图G是
3、由两个集合是由两个集合V(G)和和E(G)组成的。组成的。 其中：其中：V(G)是顶点的非空有限集，是顶点的非空有限集，E(G)是边的有限集合，是边的有限集合，边是顶点的无序对，记为边是顶点的无序对，记为（v,w）或或（w,v），并且并且（v,w)=(w,v)图的定义和术语图的定义和术语4例：有向图例：有向图245136G1图图G1中：中：V(G1)=1,2,3,4,5,6E(G1)=, , , , , , 例：无向图例：无向图157324G26图图G2中：中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6),
4、(5,7)5有向完备图有向完备图：n个顶点的有向图最大边数是个顶点的有向图最大边数是n(n-1)。无向完备图无向完备图：n个顶点的无向图最大边数是个顶点的无向图最大边数是n(n-1)/2。213213有向完备图有向完备图无向完备图无向完备图6权权：与图的边或弧相关的数。：与图的边或弧相关的数。网网：带权的图：带权的图例例14523753186427子图子图：如果图：如果图G(V,E)和图和图G(V,E),满足：满足： V V，E E，则称则称G为为G的子图。的子图。3562451363568顶点的度顶点的度 无向图中，顶点的度为与每个顶点相连的边数。无向图中，顶点的度为与每个顶点相连的边数。
5、有向图中，顶点的度分成入度与出度。有向图中，顶点的度分成入度与出度。 入度入度：以该顶点为头的弧的数目。：以该顶点为头的弧的数目。 出度出度：以该顶点为尾的弧的数目。：以该顶点为尾的弧的数目。245136G1顶点顶点2入度：入度：1 出度：出度：3顶点顶点4入度：入度：1 出度：出度：0157324G26顶点顶点5的度：的度：3顶点顶点2的度：的度：49路径路径：路径是顶点的序列：路径是顶点的序列V=Vi,0,Vi,1,Vi,n，满足满足 (Vi,j-1,Vi,j)E 或或 E，(1j n)。路径长度路径长度：沿路径边的数目或沿路径各边权值之和。：沿路径边的数目或沿路径各边权值之和。回路回路：
6、第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径简单路径：序列中顶点不重复出现的路径叫：序列中顶点不重复出现的路径叫简单回路简单回路：除了第一个顶点和最后一个顶点外，其余：除了第一个顶点和最后一个顶点外，其余 顶点不重复出现的回路。顶点不重复出现的回路。G1245136路径：路径：1，2，3，5，6，3路径长度：路径长度：5简单路径：简单路径：1，2，3，5回路：回路：1，2，3，5，6，3，1简单回路：简单回路：3，5，6，310157324G26路径：路径：1，2，5，7，6，5，2，3路径长度：路径长度：7简单路径：简单路径：1，2，5，7，6回路：回路
7、：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，111连通连通：从顶点：从顶点V到顶点到顶点W有路径，则说有路径，则说V和和W是连通的。是连通的。连通图连通图：图中任意两个顶点都是连通的图。：图中任意两个顶点都是连通的图。连通图连通图24513612连通分量连通分量：非连通图的每一个连通部分。：非连通图的每一个连通部分。强连通图强连通图：有向图中，如果对每一对：有向图中，如果对每一对Vi,Vj V, ViVj,从从Vi到到Vj 和从和从Vj到到 Vi都存在路径，则称都存在路径，则称G是强连通图。是强连通图。强连通图强连通图356245136非连通图非连通图连通分量连通分量137
8、.2 图的存储表示图的存储表示一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示14Aij=0 (i,j)VR1 (i,j)VR图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为特点：特点：对称矩阵顶点的度数顶点的度数FirstAdjVex(G, v);NextAdjVex(G, v, w);如何求如何求?ABCDEF A B C D E F 15 从无向图的邻接矩阵可以得出如下从无向图的邻接矩阵可以得出如下结论结论 （1）矩阵
9、是对称的，可压缩存储（上（下）三角）矩阵是对称的，可压缩存储（上（下）三角）;（2）第）第i行或第行或第i 列中列中1的个数为顶点的个数为顶点i 的度的度;（3）矩阵中）矩阵中1的个数的一半为图中边的数目的个数的一半为图中边的数目;（4）很很容容易易判判断断顶顶点点i 和和顶顶点点j之之间间是是否否有有边边相相连连(看看矩矩阵阵中中i行行j列值是否为列值是否为1)。0111101011011010 16有向图的邻接矩阵有向图的邻接矩阵ABECD 从有向图的邻接矩阵可以得出如下从有向图的邻接矩阵可以得出如下结论结论（1） 矩阵不一定是对称的矩阵不一定是对称的;（2） 第第i 行中行中1的个数为顶
10、点的个数为顶点i 的出度的出度;（3） 第第i列中列中1的个数为顶点的个数为顶点 i的入度的入度;（4） 矩阵中矩阵中1的个数为图中弧的数目的个数为图中弧的数目;（5） 很容易判断顶点很容易判断顶点i 和顶点和顶点j 是否有弧相连是否有弧相连.ABCDE A B C D E 17网的邻接矩阵表示网的邻接矩阵表示 类似地可以定义网的邻接矩阵为：类似地可以定义网的邻接矩阵为： wij 若（若（i,j）E(G)或或i,jE(G) 其它情形其它情形Aij=12345 1 2 3 4 5 18const MAX_VERTEX_NUM = 20;/ 最大顶点个数最大顶点个数typedef enum DG,
11、 DN, AG, AN GraphKind; / 类型标志类型标志有向图有向图,有向网有向网,无向图无向图,无向网无向网typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。是顶点关系类型。/ 对无权图，用对无权图，用1或或0表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义图的定义VertexType vexsM
12、AX_VERTEX_NUM; / 顶点信息顶点信息AdjMatrix arcs; / 表示顶点之间关系的二维数组表示顶点之间关系的二维数组int vexnum, arcnum; / 图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind kind; / 图的种类标志图的种类标志 MGraph; 图的图的C语言描述语言描述19 容易实现图的操作，如：求某顶点的度、判断顶点之容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。间是否有边（弧）、找顶点的邻接点等等。 n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边( (弧弧););空间效率为
13、空间效率为O(nO(n2 2) )。 邻接矩阵存储方式的邻接矩阵存储方式的优点：优点：邻接矩阵邻接矩阵存储方式存储方式缺点：缺点：20 图的邻接表存储表示图的邻接表存储表示顶点的度数顶点的度数FirstAdjVex(G, v);NextAdjVex(G, v, w);如何求如何求?例例1234acdbdata firstarc 4 2 1 2adjvexnext5e 4 3 5 1 5 3 2 3aecbdG21234521有向图的邻接表有向图的邻接表顶点的出度和入度顶点的出度和入度FirstAdjVex(G, v);NextAdjVex(G, v, w);如何求如何求?1234acdbdat
14、a firstarc 2 3 4 1adjvexnext例例G1bdac123422有向图的逆邻接表有向图的逆邻接表在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧。例例G1bdac12341234acdbdata firstarc 4 1 adjvexnext 1323typedef struct ArcNode int adjvex; / 该弧所指向的顶点的下标该弧所指向的顶点的下标 struct ArcNode *nextarc; / 指向下一条弧的指针指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 ArcNode;adjvex nex
15、tarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data; / 顶点信息顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构顶点的结点结构24typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志图的种类标志 ALGraph;图的结构定义图的结构定义例例G1bdac12341234acdbdata fi
16、rstarc 4 1 adjvexnext 1325已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存储结构形成后，图便成后，图便唯一确定！唯一确定！26讨论：邻接表与邻接矩阵有什么讨论：邻接表与邻接矩阵有什么异同异同之处？之处？1. 1. 联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2. 2. 区别：区别： 对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（
17、行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。 邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的空间复而邻接表的空间复杂度为杂度为O(n+e)O(n+e)。3. 3. 用途：用途：邻接矩阵多用于稠密图的存储（邻接矩阵多用于稠密图的存储（e e接近接近n(n-n(n-1)/2)1)/2)；而邻接表多用于稀疏图的存储（；而邻接表多用于稀疏图的存储（enen2 2) )27弧结点：弧结点：typedef struct arcnode int tailvex, headvex; /弧尾、弧
18、头在表头数组中位置弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧指向弧头相同的下一条弧 struct arcnode *tlink; /指向弧尾相同的下一条弧指向弧尾相同的下一条弧arcbox;tailvex headvex hlink tlink顶点结点：顶点结点：typedef struct vexnode int data; /存与顶点有关信息存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout; /指向以该顶
19、点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点vexNode;data firstin firstout有向图的十字链表表示法有向图的十字链表表示法28typedef struct / 十字链表结构定义十字链表结构定义VexNode xlistMAX_VERTEX_NUM; / 表头向量表头向量int vexnum, arcnum; / 有向图的当前顶点数和弧数有向图的当前顶点数和弧数GraphKind kind; / 图的种类标志图的种类标志 OLGraph; 29ab cd12341 31 23 43 14 34 24 1例例bdac123430顶点结点顶点结点：typedef s
20、truct dnode int data; /存与顶点有关的信息存与顶点有关的信息 struct node *firstedge; /指向第一条依附于该顶点的边指向第一条依附于该顶点的边vexnode;data firstedge边结点边结点：typedef struct node int mark; / 访问访问标记域标记域 int ivex, jvex; /该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 struct node *ilink, *jlink; /分别指向依附于分别指向依附于ivex和和jvex的下一条边的下一条边EgeNode;mark ivex il
21、ink jvex jlink无向图的邻接多重表表示法无向图的邻接多重表表示法31typedef struct / 多重链表结构定义VexNode adjmulistMAX_VERTEX_NUM;int vexnum, edgenum; / 无向图的当前顶点数和边数GraphKind kind; / 图的种类标志 AMLGraph; 32例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 233各种存储结构的适用类型w数组：数组： 有向图和无向图有向图和无向图 w邻接表（逆邻接表）：有向图和无向图邻接表（逆邻接表）：有向图和无向图 n十字链表：十字链表： 有向图有向图
22、 n邻接多重表：邻接多重表： 无向图无向图347.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例351、深度优先遍历、深度优先遍历(DFS)方法方法：从图的某一顶点：从图的某一顶点V0出发，访问此顶点；然后依次从出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所的未被访问的邻接点出发，深度优先遍历图，直至图中所有和有和V0相通的顶点都被访问到；若此时
23、图中尚有顶点未被访相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。直至图中所有顶点都被访问为止。36例例2V1V2V4V5V3V7V6V8深度遍历：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例1深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V524513637V1V2V4V5V3V7V6V8深度遍历：深度遍历：V112341342vexdatafirstarc 2 7 8 3adjvexnext5
24、5 6 4 1 5 1 2 8 2678678 7 3 6 3 5 4V3 V7 V6 V2 V5 V8 V438开始开始访问访问V0,置标志置标志求求V0邻接点邻接点有邻接点有邻接点w求下一邻接点求下一邻接点wV0W访问过访问过结束结束NYNYDFS开始开始标志数组初始化标志数组初始化Vi=1Vi访问过访问过DFSVi=Vi+1Vi=Vexnums结束结束NNYY 深度优先遍历算法：递归算法深度优先遍历算法：递归算法39V1V2V4V5V3V7V6V812341342data firstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V3
25、 V7 V6 V2 V4 V8 V5 void DFS(Graph G, int v) / 从顶点从顶点v出发，深度优先搜索遍历图出发，深度优先搜索遍历图 G visitedv = TRUE; VisitFunc (v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w / 递归调用递归调用DFS / DFS问题？问题？按该存储结构得到的按该存储结构得到的遍历次序是否唯一遍历次序是否唯一？40void DFSTraverse(ALGra
26、ph G) / 对以邻接表表示的图对以邻接表表示的图G作深度优先遍历作深度优先遍历bool visitedG.vexnum; / 附设访问标识数组for (v=0; vG.vexnum; +v)visitedv = FALSE; / 访问标识数组初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); / 对尚未访问的顶点调用DFS 41广度优先搜索遍历图广度优先搜索遍历图方法：从图的某一顶点方法：从图的某一顶点V0出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，的各个未曾访问过的
27、邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止都被访问为止V1V2V4V5V3V7V6V8例广度遍历广度遍历：V1 V2 V3 V4 V5 V6 V7 V842V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7
28、 V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8V1V2V4V5V3V7V6V8例广度遍历：广度遍历：V1 V2 V3 V4 V6 V7 V8 V543例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 4 51fr遍历序列：10 1 2 3 4 54fr遍历序列：1 4f0 1 2 3 4 54 3r遍历序列：1 4 344例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3
29、4 54 3 2fr遍历序列：1 4 3 20 1 2 3 4 5 3 2fr遍历序列：1 4 3 2f0 1 2 3 4 5 3 2 5r遍历序列：1 4 3 2 5450 1 2 3 4 5 2 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 5fr遍历序列：1 4 3 2 50 1 2 3 4 5 fr遍历序列：1 4 3 2 5例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 246 void BFSTraverse(Graph G, Status (*Visit)(int v)for (v=0
30、; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 visitedu = TRUE; Visit(u); / 访问u EnQueue(Q, v); / v入队列 / BFSTraverseV1V2V4V5V3V7V6V8例while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为ufor(w=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G
31、,u,w)if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while 47定义定义:所有顶点均由边连接在一起，但不存在回路的图。所有顶点均由边连接在一起，但不存在回路的图。深度优先深度优先 生成树与广度优先生成树与广度优先 生成树。生成树。生成森林生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森：非连通图每个连通分量的生成树一起组成非连通图的生成森林。林。说明说明（1）一个图可以有许多棵不同的生成树）一个图可以有许多棵不同的生成树（2）所有生成树具有以下共同特点：）所有生成树具
32、有以下共同特点： 生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图生成树是图的极小连通子图 一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边 生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路 含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树生成树48V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8
33、V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8深度优先生成树深度优先生成树广度优先生成树广度优先生成树49例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林50问题提出问题提出：要在要在n个城市间建立通信联络网，顶点表示城市，权表示城市间建立个城市间建立通信联络网，顶点表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小。之和（即建立该通信
34、网所需花费的总代价）最小。问题分析问题分析：n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路条线路n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路条线路问题转化为：问题转化为：如何在可能的线路中选择如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。且总耗费（各边权值之和）最小。1654327131791812752410最小生成树最小生成树51方法一：普里姆方法一：普里姆(Prim)算法算法算法思想算法思想：设：设N=(V,E)是连通网，是连通网，TE是是N上最小生成树中边上最小生成树中边
35、的集合。的集合。(1)初始令初始令U=u0,(u0V), TE= ; (2)在所有在所有uU,vV-U的边的边(u,v)E中，找一条代价最小的中，找一条代价最小的边边(u0,v0)并入集合并入集合TE，同时同时v0并入并入U;(3)重复上述操作直至重复上述操作直至U=V为止，则为止，则T=(V,TE)为为N的最小生的最小生成树。成树。算法实现算法实现：图用邻接矩阵表示：图用邻接矩阵表示算法评价算法评价：T(n)=O(n)构造最小生成树方法构造最小生成树方法52例例1654326513566425131163141643142116432142516543214253从从V1开始构造，即开始构造
36、，即U=V153struct VertexType adjvex; / U集合中的顶点序号集合中的顶点序号 VRType lowcost; /和顶点集和顶点集U中顶点相连中顶点相连接的最小代价接的最小代价 closedgeMAX_VERTEX_NUM;设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中的每个顶点，集中的每个顶点，记录和顶点集记录和顶点集U中顶点相连接的代价最小的边：中顶点相连接的代价最小的边：54abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5UV-Uab,c,d,e,f,ga,eb,c
37、,d,f,ga,e,db,c, f,ga,e,d,cb, f,ga,e,d,c,bf,ga b c d e f ggf55const MAX_VERTEX_NUM = 20;/ 最大顶点个数最大顶点个数typedef enum DG, DN, AG, AN GraphKind; / 类型标志类型标志有向图有向图,有向网有向网,无向图无向图,无向网无向网typedef struct ArcCell / 弧的定义弧的定义 VRType adj; / VRType是顶点关系类型。是顶点关系类型。/ 对无权图，用对无权图，用1或或0表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型
38、。InfoType *info; / 该弧相关信息的指针该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 图的定义图的定义VertexType vexsMAX_VERTEX_NUM; / 顶点信息顶点信息AdjMatrix arcs; / 表示顶点之间关系的二维数组表示顶点之间关系的二维数组int vexnum, arcnum; / 图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind kind; / 图的种类标志图的种类标志 MGraph; 图的邻接矩阵存储表示的图的邻接矩阵存储表示的C语言描述语言
39、描述56void MiniSpanTree_P(MGraph G, VertexType u) void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点用普里姆算法从顶点u u出发构造网出发构造网G G的最小生成树的最小生成树 k = LocateVex ( G, u ); k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / for ( j=0; jG.vexnum; +j ) / 辅助数组初始化辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ;
40、 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / closedgek.lowcost = 0; / 初始，初始，U Uuu for (i=1; iG.vexnum; +i) for (i=1; iG.vexnum; +i) k = minimum(closedge); k = minimum(closedge); / / 求出加入生成树的下一个顶点求出加入生成树的下一个顶点(k)(k) printf(closedgek.adjvex, G.vexsk); printf(closedgek.adjvex, G.ve
41、xsk); / / 输出生成树上一条边输出生成树上一条边 closedgek.lowcost = 0; closedgek.lowcost = 0; / / 第第k k顶点并入顶点并入U U集集 for (j=0; jG.vexnum; +j) for (j=0; jG.vexnum; +j) /修改修改closedgeclosedge数组数组 if (G.arcskj.adj closedgej.lowcost) if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; closedgej = G.vexs
42、k, G.arcskj.adj ; 57165432651356642516543212345方法二：克鲁斯卡尔方法二：克鲁斯卡尔(Kruskal)算法算法算法思想：设连通网算法思想：设连通网N=(V,E)，令最小生成树令最小生成树（1）初始状态为只有）初始状态为只有n个顶点而无边的非连通图个顶点而无边的非连通图T=(V, )，每个顶点自成一个连通分量；每个顶点自成一个连通分量；（2）在）在E中选取代价最小的边，若该边依附的顶点落在中选取代价最小的边，若该边依附的顶点落在T中不中不同的连通分量上，则将此边加入到同的连通分量上，则将此边加入到T中；否则，舍去此边，选中；否则，舍去此边，选取下一条
43、代价最小的边；取下一条代价最小的边；（3）依此类推，直至）依此类推，直至T中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。58（0）用顶点数组和边数组存放顶点和边信息）用顶点数组和边数组存放顶点和边信息（1）初始时，令每个顶点的）初始时，令每个顶点的jihe互不相同；每个边的互不相同；每个边的flag为为0（2）选出权值最小且）选出权值最小且flag为为0的边的边（3）若该边依附的两个顶点的）若该边依附的两个顶点的jihe 值不同，即非连通，则令值不同，即非连通，则令 该边的该边的flag=1, 选中该边；再令该边依附的两顶点的选中该边；再令该边依附的两顶点的jihe 以及
44、两集合中所有顶点的以及两集合中所有顶点的jihe 相同相同 若该边依附的两个顶点的若该边依附的两个顶点的jihe 值相同，即连通，则令该值相同，即连通，则令该 边的边的flag=2, 即舍去该边即舍去该边（4）重复上述步骤，直到选出）重复上述步骤，直到选出n-1条边为止条边为止 顶点结点：顶点结点：typedef struct int data; /顶点信息顶点信息 int jihe; VEX;边结点：边结点：typedef struct int vexh, vext; /边依附的两顶点边依附的两顶点 int weight; /边的权值边的权值 int flag; /标志域标志域EDGE;算法
45、实现算法实现59例例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222算法描述算法描述260普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围两种算法的比较61问题提出问题提出：学生选修课程问题学生选修课程问题顶点表示课程，有向弧表示先决条件，若课程顶点表示课程，有向弧表示先决条件，若课程i是课程是课程
46、j的先决条件，则图中有弧的先决条件，则图中有弧，学生应按怎样的顺序，学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业，这就牵学习这些课程，才能无矛盾、顺利地完成学业，这就牵涉到涉到拓扑排序拓扑排序。 拓扑排序拓扑排序62定义定义AOV网网：用顶点表示活动，用弧表示活动间优先关系：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网的有向图称为顶点表示活动的网(Activity On Vertex network)，简称简称AOV网。网。若若是图中有向边，则是图中有向边，则vi是是vj的的直接前驱直接前驱；vj是是vi的的直接后继。直接后继。AOV网中不允许有回路，否则意
47、味着某项活动以自己网中不允许有回路，否则意味着某项活动以自己为先决条件。为先决条件。拓扑排序拓扑排序：把：把AOV网络中各顶点按照它们相互之间的网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。优先关系排列成一个线性序列的过程。检测检测AOV网中是否存在环方法：对有向图构造其顶点网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该列中，则该AOV网必定不存在环。网必定不存在环。63拓扑排序的方法拓扑排序的方法（1）在有向图中选一个）在有向图中选一个没有前驱的顶点没有前驱的顶点且输出之；且输
48、出之；（2）从图中）从图中删除删除该顶点和所有以它为尾的弧；该顶点和所有以它为尾的弧；（3）重复上述两步，直至全部顶点均已输出；或）重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止者当图中不存在无前驱的顶点为止64课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓
49、扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8注意：一个注意：一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的65C1C2C3C4C5C6C7C8C9C10C11C12（1）先选择没有前驱的顶点）先选择没有前驱的顶点C1，删除删除C1和所有以它为尾和所有以它为尾的弧。的弧。66C2C3C4C5C6C7C8C9C10C11C12C3C4C5C6C7C8C9C10C11C12（2）选择没有前驱的顶点）选择没有前驱的顶点C2，删除删除C2和所有以它为和所有以它为尾的弧。尾的
50、弧。拓扑序列：拓扑序列：C1-C2（3）选择没有前驱的顶）选择没有前驱的顶点点C3，删除删除C3和所有以和所有以它为尾的弧。它为尾的弧。拓扑序列：拓扑序列：C1-C2-C367C4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C12（4）选择没有前驱的顶点）选择没有前驱的顶点C4，删除删除C4和所有以它为和所有以它为尾的弧。尾的弧。拓扑序列：拓扑序列：C1-C2-C3-C4（5）选择没有前驱的顶点）选择没有前驱的顶点C5，删除删除C5和所有以它为和所有以它为尾的弧。尾的弧。拓扑序列：拓扑序列：C1-C2-C3-C4C568C6C8C11C12拓扑序列：拓扑序列：C1-C
51、2-C3-C4-C5-C7-C9-C10-C11（9）C6C7C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7（6）C6C8C9C10C11C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9（7）C6C8C10C11C12拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10（8）69C6C8C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6（10）C8C12拓扑序列：拓扑序列：C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12（11）C8拓扑序列：拓扑序列：C1-C2-C3-C4-C
52、5-C7-C9-C10-C11-C6-C12-C8（12）70那么如何进行拓扑排序？步骤如下：那么如何进行拓扑排序？步骤如下：（1） 在在AOV网中选择一个没有前驱的顶点并输出；网中选择一个没有前驱的顶点并输出；（2） 从从AOV网中删除该顶点以及从它出发的弧；网中删除该顶点以及从它出发的弧；重复以上两步直至重复以上两步直至AOV网变空（即已输出所有顶点）网变空（即已输出所有顶点） 或者剩余子图中不存在没有前驱的顶点。或者剩余子图中不存在没有前驱的顶点。 后一种情况则说明该后一种情况则说明该AOV网中含网中含有向环有向环。如右所示如右所示AOV网的拓扑排序的过程如动画所示。网的拓扑排序的过程如
53、动画所示。 图中存在一个有向环，则在拓扑排序输出顶点图中存在一个有向环，则在拓扑排序输出顶点c之后就之后就找不到找不到没有前驱没有前驱的顶点了的顶点了 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减171算法实现算法实现（1）以邻接表作存储结构）以邻接表作存储结构;（2）把邻接表中所有入度为）把邻接表中所有入度为0的顶点进栈的顶点进栈,便于查询便于查询;（3）栈非空时，输出栈顶元素）栈非空时，输出栈顶元素Vj并退栈；在邻接表并退栈；在邻接表中查找中查找Vj的直接后继的直接后继Vk，把，把Vk的入度减的入度
54、减1；若；若Vk的入的入度为度为0则进栈则进栈; (4)重复上述操作直至栈空为止。若栈空时输出的顶重复上述操作直至栈空为止。若栈空时输出的顶点个数不是点个数不是n，则有向图有环；否则，拓扑排序完毕则有向图有环；否则，拓扑排序完毕7232104算法描述算法描述例1234560122indegree firstarc 5 5 4 3adjvex nextarc3 2 5 2 40123456top16toptop730122indegree firstarc 5 5 4 3adjvex nextarc3 2 5 2 40123456输出序列：63210416toptop例123456740122i
55、ndegree firstarc 5 5 4 3adivex nextarc3 2 5 2 40123456输出序列：6321041topp例123456750122indegree firstarc 5 5 4 3adjvex nextarc2 2 5 2 40123456输出序列：6321041topp例123456760122Indegree firstarc 5 5 4 3adjvex nextarc2 2 5 2 40123456输出序列：6321041topp例123456770112indegree firstarc 5 5 4 3adjvex nextarc2 2 5 2 40
56、123456输出序列：6321041topp例123456780112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6321041topp=NULL例123456790112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 1321041toptop例123456800112inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104topp例123456810102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104top
57、p4例123456820102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top例123456830102inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top例123456840002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top3例123456850002inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top3例123456860002inlink
58、5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top3例123456870001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p4top3例123456880001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 132104p=NULL4top3例123456890001inlink 5 5 4 3vex next2 2 5 2 40123456输出序列：6 1 3321044top3例123456900001inlink 5 5 4 3vex nex
59、t2 2 5 2 40123456输出序列：6 1 3321044topp例123456910001inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp例123456920001inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp例123456930000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044topp2例123456940000inlink 5 5 4 3vex next1 2 5 2 401234
60、56输出序列：6 1 3321044topp2例123456950000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3321044top2p=NULL例123456960000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2321044top2p=NULL例123456970000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2321044topp=NULL例123456980000inlink 5 5 4 3vex next1 2 5 2
61、40123456输出序列：6 1 3 2 4321044top例123456990000inlink 5 5 4 3vex next1 2 5 2 40123456输出序列：6 1 3 2 432104topp例1234561000000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp5例1234561010000inlink 5 5 4 3vex next0 2 5 2 40123456输出序列：6 1 3 2 432104topp=NULL5例1234561020000inlink 5 5 4 3vex next0
62、2 5 2 40123456输出序列：6 1 3 2 4 532104top5例1234561030000indegree firstarc 5 5 4 3Adjvex nextarc0 2 5 2 40123456输出序列：6 1 3 2 4 532104topp=NULL例123456104CountInDegree(G,indegree); /对各顶点求入度对各顶点求入度InitStack(S);for ( i=0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度为零的顶点入栈入度为零的顶点入栈count=0; /对输出顶点计数对输出顶点计数
63、while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(G,v); w!=0; w=NextAdj(G,v,w) -indegree(w); / 弧头顶点的入度减一弧头顶点的入度减一 if (!indegreew) Push(S, w); /新产生的入度为零的顶点入新产生的入度为零的顶点入栈栈 if (countG.vexnum) printf(“图中有回路图中有回路”)Else return OK105987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4
64、关键路径关键路径问题提出问题提出:把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。在它之前的活动已完成，在它之后的活动可以开始。例例 设一个工程有设一个工程有11项活动，项活动，9个事件。个事件。事件事件 V1表示整个工程开始，事件表示整个工程开始，事件V9表示整个工程结束。表示整个工程结束。问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？106 如何求关键活动？如何
65、求关键活动？ve(j) =事件事件Vj的最早发生时间的最早发生时间(从源点到顶点从源点到顶点j的最长路径长度的最长路径长度)vl(j) =事件事件Vj的最迟发生时间的最迟发生时间e(i)表示活动表示活动ai的最早开始时间的最早开始时间l(i)表示活动表示活动ai的最迟开始时间的最迟开始时间关键活动关键活动关键路径上的活动叫关键路径上的活动叫，即，即l(i)=e(i)的活动的活动abcdefghk645211972446174源点汇点107设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()jk
66、ai如何求如何求Ve(j)和和Vl(j)？(2)从从Vl(n)=Ve(n)开始向后递推开始向后递推987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4l如何找如何找e(i)=l(i)的关键活动？的关键活动？(1)从从Ve(1)=0开始向前递推开始向前递推108求关键路径步骤求关键路径步骤求求Ve(i)求求Vl(j)求求e(i) (e(i)=Ve(j)求求l(i) (Vl(k)-dut()计算计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4
67、V5V6V7V8V9顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动 e l l-e00002266046258377077071031616014140033109问题：问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和为最小的一条路径边上权值之和为最小的一条路径最短路径最短路径从某个源点到其余各顶点的最短路径迪杰斯特拉从某个源点到其余各顶点的最短路径迪杰斯特拉Dijkstra算法算法51643208562301371732913长度最短路径81321
68、2019求每一对顶点之间的最短路径弗洛伊德求每一对顶点之间的最短路径弗洛伊德Floyed算算法法最短路径最短路径110 设置辅助数组设置辅助数组DistDist，其中每个分量，其中每个分量Distk Distk 表示表示 当前所求得当前所求得的从源点到其余各顶点的从源点到其余各顶点 k k 的最短路径。的最短路径。1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。最短路径。2）修改其它各顶点的）修改其它各顶点的Distk值。值。假设求得最短路径的顶点为假设求得最短路径的顶点为u，若，若 Distu+G.arcsukDis
69、tk则将则将 Distk 改为改为 Distu+G.arcsuk。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度其中的最小值即为最短路径的长度。1 Dijkstra算法的基本思想算法的基本思想 按按路路径径长长度度递递增增顺顺序序求求最最短短路路径径算算法法 ,与与求求最最小小生生成成树树的的普普里里姆姆算法类似算法类似1111383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:205164320856230137173298V0,V213V0
70、,V113V0,V2,V319V0,V2,V3,V420112算法实现算法实现（1）图用带权邻接矩阵存储。）图用带权邻接矩阵存储。（2）数组数组dist 存放当前找到的从源点存放当前找到的从源点V0到每到每个终点的最短路径长度，其初态为图中直接路个终点的最短路径长度，其初态为图中直接路径权值。径权值。（3）数组）数组pre 表示从表示从V0到各终点的最短路径到各终点的最短路径上，此顶点的前一顶点的序号；若从上，此顶点的前一顶点的序号；若从V0到某终到某终点无路径，则用点无路径，则用0作为其前一顶点的序号。作为其前一顶点的序号。113算法描述算法描述627543185623013717329di
71、st1 2 3 4 5 6 70 13 8 30 32pre1 2 3 4 5 6 70 1 1 0 1 0 1(1)k=113322 2022194215长度长度最短路径最短路径13813192120算法分析：算法分析：T(n)=O(n)114每一对顶点之间的最短路径每一对顶点之间的最短路径方法一方法一：每次以一个顶点为源点，重复执行：每次以一个顶点为源点，重复执行Dijkstra算法算法n次次 T(n)=O(n)方法二方法二：弗洛伊德：弗洛伊德(Floyd)算法算法算法思想：逐个顶点试探法算法思想：逐个顶点试探法求最短路径步骤：求最短路径步骤：（1）初始时设置一个）初始时设置一个n阶方阵，
72、令其对角线元素为阶方阵，令其对角线元素为0，若，若存在弧存在弧，则对应元素为权值；否则为则对应元素为权值；否则为。 （2）逐步试着在原直接路径中增加中间顶点，若加入中）逐步试着在原直接路径中增加中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值。间点后路径变短，则修改之；否则，维持原值。（3）所有顶点试探完毕，算法结束。）所有顶点试探完毕，算法结束。115例例ACB2643110 4 116 0 23 0初始：初始：路径：路径：AB ACBA BCCA0 4 66 0 23 7 0加入加入B：路径：路径：AB ABCBA BCCA CAB0 4 116 0 23 7 0加入加入A：路径
73、：路径：AB ACBA BCCA CAB0 4 65 0 23 7 0加入加入C：路径：路径：AB ABCBCA BCCA CAB116例例132264311初始：初始：0 4 116 0 23 0length=0 1 12 0 23 0 0path=加入加入V1：0 4 116 0 23 7 0length=0 1 12 0 23 1 0path=加入加入V2：0 4 66 0 23 7 0length=0 1 22 0 23 1 0path=加入加入V3：0 4 65 0 23 7 0length=0 1 23 0 23 1 0path=算法实现算法实现（1）图用邻接矩阵存储）图用邻接矩阵
74、存储（2）length存放最短路径长度存放最短路径长度（3）pathij是从是从Vi到到Vj的最短路径上的最短路径上Vj前一顶点序号前一顶点序号1171.1.掌握图结构的基本概念掌握图结构的基本概念2.2.熟悉图的熟悉图的邻接矩阵和邻接表存储结构。邻接矩阵和邻接表存储结构。3.3.熟练掌握图的熟练掌握图的两种搜索路径的遍历两种搜索路径的遍历。在学习中应注在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异意图的遍历算法与树的遍历算法之间的类似和差异。4.4.图的应用图的应用 最小生成树最小生成树拓扑排序拓扑排序关键路径关键路径最短路径最短路径从一点到其余各点的最短路径从一点到其余各点的最短路径每对顶点的最短路径每对顶点的最短路径本章学习要点本章学习要点118
