《图及其应用》PPT课件.ppt

《《图及其应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图及其应用》PPT课件.ppt（118页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、17.1 抽象数据类型图的定义抽象数据类型图的定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树 最短路径问题最短路径问题 拓扑排序拓扑排序、关键路径、关键路径21.熟悉图的各种熟悉图的各种存储结构存储结构及其及其构造算法构造算法，了解实际问题的求解效率，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的熟练掌握图的两种搜索路径的遍历遍历：深度优先搜索和广度优先搜：深度优先搜索和广度优先搜索的算法。索的算法。3.图的算法应用。图的算法应用。学习提要学习提要3图图(Graph)：图：图

2、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),(5,7)5有向完备图有向完备图：n个顶点的有向图最大边

4、数是个顶点的有向图最大边数是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回路：回路：1，2，5，7，6，5，2，1简单回路：简单回路：1，2，3，

7、111连通连通：从顶点：从顶点V到顶点到顶点W有路径，则说有路径，则说V和和W是连通的。是连通的。连通图连通图：图中任意两个顶点都是连通的图。：图中任意两个顶点都是连通的图。连通图连通图24513612连通分量连通分量：非连通图的每一个连通部分。：非连通图的每一个连通部分。强连通图强连通图：有向图中，如果对每一对：有向图中，如果对每一对Vi,Vj V,ViVj,从从Vi到到Vj 和从和从Vj到到 Vi都存在路径，则称都存在路径，则称G是强连通图。是强连通图。强连通图强连通图356245136非连通图非连通图连通分量连通分量137.2 图的存储表示图的存储表示一、图的数组(邻接矩阵)存储表示二、

8、图的邻接表存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示四、无向图的邻接多重表存储表示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的个数为顶点的个数为顶点i 的出度的出度;（3）第第i列中列中1的个数为顶点的个数为顶点

10、 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,DN,AG,AN GraphKind;/类型标志类型标志有向图有向图,有向网有向网,无向图无向

11、图,无向网无向网typedef struct ArcCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。是顶点关系类型。/对无权图，用对无权图，用1或或0表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型。InfoType*info;/该弧相关信息的指针该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义VertexType vexsMAX_VERTEX_NUM;/顶点信息顶点信息AdjMatrix arcs;/表示顶点之间关系的二维数组表示顶点之间关系

12、的二维数组int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind kind;/图的种类标志图的种类标志 MGraph;图的图的C语言描述语言描述19 容易实现图的操作，如：求某顶点的度、判断顶点之容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。间是否有边（弧）、找顶点的邻接点等等。n n个顶点需要个顶点需要n*nn*n个单元存储边个单元存储边(弧弧););空间效率为空间效率为O(nO(n2 2)。邻接矩阵存储方式的邻接矩阵存储方式的优点：优点：邻接矩阵邻接矩阵存储方式存储方式缺点：缺点：20 图的邻接表存储表

13、示图的邻接表存储表示顶点的度数顶点的度数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);如何求如何求?1234acdbdata firstarc 2 3 4 1adjvexnext例例G1bdac123422有向图的逆邻接表有向图的逆邻接表在有向图的邻接表中，对每个顶点，链接的是指向该顶

14、点的弧。例例G1bdac12341234acdbdata firstarc 4 1 adjvexnext 1323typedef struct ArcNode int adjvex;/该弧所指向的顶点的下标该弧所指向的顶点的下标 struct ArcNode *nextarc;/指向下一条弧的指针指向下一条弧的指针 InfoType *info;/该弧相关信息的指针该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data;/顶点信息顶点信息 ArcNode *firstarc;/指

15、向第一条依附该顶点的弧指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;data firstarc顶点的结点结构顶点的结点结构24typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志图的种类标志 ALGraph;图的结构定义图的结构定义例例G1bdac12341234acdbdata firstarc 4 1 adjvexnext 1325已知某网的邻接（出边）表，请画出该网络。已知某网的邻接（出边）表，请画出该网络。8064125当邻接表的当邻接表的存储结构形存储结构形成后，图便成

16、后，图便唯一确定！唯一确定！26讨论：邻接表与邻接矩阵有什么讨论：邻接表与邻接矩阵有什么异同异同之处？之处？1.1.联系：联系：邻接表中每个链表对应于邻接矩阵中的一行，邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。链表中结点个数等于一行中非零元素的个数。2.2.区别：区别：对于任一确定的无向图，邻接矩阵是唯一的（行列对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。与顶点编号无关）。邻接矩阵的空间复杂度为邻接矩阵的空间复杂度为O(nO(n2 2),),而邻接表的

17、空间复而邻接表的空间复杂度为杂度为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;/弧尾、弧头在表头数组中位置弧尾、弧头在表头数组中位置 struct arcnode *hlink；/指向弧头相同的下一条弧指向弧头相同的下一条弧 struct arcnode *tlink;/指向弧尾相同的下一条弧指向弧尾相同的下

18、一条弧arcbox;tailvex headvex hlink tlink顶点结点：顶点结点：typedef struct vexnode int data;/存与顶点有关信息存与顶点有关信息 struct arcnode *firstin；/指向以该顶点为弧头的第一个弧结点指向以该顶点为弧头的第一个弧结点 struct arcnode *firstout;/指向以该顶点为弧尾的第一个弧结点指向以该顶点为弧尾的第一个弧结点vexNode;data firstin firstout有向图的十字链表表示法有向图的十字链表表示法28typedef struct /十字链表结构定义十字链表结构定义Ve

19、xNode xlistMAX_VERTEX_NUM;/表头向量表头向量int vexnum,arcnum;/有向图的当前顶点数和弧数有向图的当前顶点数和弧数GraphKind kind;/图的种类标志图的种类标志 OLGraph;29ab cd12341 31 23 43 14 34 24 1例例bdac123430顶点结点顶点结点：typedef struct dnode int data;/存与顶点有关的信息存与顶点有关的信息 struct node *firstedge;/指向第一条依附于该顶点的边指向第一条依附于该顶点的边vexnode;data firstedge边结点边结点：typ

20、edef struct node int mark;/访问访问标记域标记域 int ivex,jvex;/该边依附的两个顶点在表头数组中位置该边依附的两个顶点在表头数组中位置 struct node *ilink,*jlink;/分别指向依附于分别指向依附于ivex和和jvex的下一条边的下一条边EgeNode;mark ivex ilink jvex jlink无向图的邻接多重表表示法无向图的邻接多重表表示法31typedef struct /多重链表结构定义VexNode adjmulistMAX_VERTEX_NUM;int vexnum,edgenum;/无向图的当前顶点数和边数Gra

21、phKind kind;/图的种类标志 AMLGraph;32例例aecbd1234acdb5e 1 2 1 4 3 4 3 2 3 5 5 233各种存储结构的适用类型w数组：数组：有向图和无向图有向图和无向图 w邻接表（逆邻接表）：有向图和无向图邻接表（逆邻接表）：有向图和无向图 n十字链表：十字链表：有向图有向图 n邻接多重表：邻接多重表：无向图无向图347.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优

22、先搜索遍历应用举例遍历应用举例351、深度优先遍历、深度优先遍历(DFS)方法方法：从图的某一顶点：从图的某一顶点V0出发，访问此顶点；然后依次从出发，访问此顶点；然后依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所的未被访问的邻接点出发，深度优先遍历图，直至图中所有和有和V0相通的顶点都被访问到；若此时图中尚有顶点未被访相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。直至图中所有顶点都被访问为止。36例例2V1V2V4V5V3V7V6V8深度遍历

23、：深度遍历：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例例1深度遍历：深度遍历：V1 V2 V4 V8 V3 V6 V7 V524513637V1V2V4V5V3V7V6V8深度遍历：深度遍历：V112341342vexdatafirstarc 2 7 8 3adjvexnext55 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开始开始标志数组初始化标志数组

24、初始化Vi=1Vi访问过访问过DFSVi=Vi+1Vi=Vexnums结束结束NNYY 深度优先遍历算法：递归算法深度优先遍历算法：递归算法39V1V2V4V5V3V7V6V812341342data firstarc 2 7 8 3adjvexnext55 6 4 8 2678678 7深度遍历：深度遍历：V1V3 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=NextAdj

25、Vex(G,v,w)if(!visitedw)DFS(G,w);/对对v的尚未访问的邻接顶点的尚未访问的邻接顶点w /递归调用递归调用DFS /DFS问题？问题？按该存储结构得到的按该存储结构得到的遍历次序是否唯一遍历次序是否唯一？40void DFSTraverse(ALGraph G)/对以邻接表表示的图对以邻接表表示的图G作深度优先遍历作深度优先遍历bool;/附设访问标识数组for(v=0;v;+v)visitedv=FALSE;/访问标识数组初始化for(v=0;v;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS 41广度优先搜索遍历图广度优先搜索遍历

26、图方法：从图的某一顶点方法：从图的某一顶点V0出发，访问此顶点后，依次访问出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止都被访问为止V1V2V4V5V3V7V6V8例广度遍历广度遍历：V

27、1 V2 V3 V4 V5 V6 V7 V842V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 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 3

28、r遍历序列：1 4 344例1423512341342vexdata firstarc 5 5 4 3adjvex next55 1 5 1 1 4 3 2 20 1 2 3 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 3

29、adjvex next55 1 5 1 1 4 3 2 246 void BFSTraverse(Graph G,Status(*Visit)(int v)for(v=0;v;+v)visitedv=FALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;v;+v)if(!visitedv)/v 尚未访问 visitedu=TRUE;Visit(u);/访问u EnQueue(Q,v);/v入队列/BFSTraverseV1V2V4V5V3V7V6V8例while(!QueueEmpty(Q)DeQueue(Q,u);/队头元素出队并置为ufor(w=Fir

30、stAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)visitedw=TRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列 /if/while 47定义定义:所有顶点均由边连接在一起，但不存在回路的图。所有顶点均由边连接在一起，但不存在回路的图。深度优先深度优先 生成树与广度优先生成树与广度优先 生成树。生成树。生成森林生成森林：非连通图每个连通分量的生成树一起组成非连通图的生成森：非连通图每个连通分量的生成树一起组成非连通图的生成森林。林。说明说明（1）一个图可以有许多棵不同的生成树）一个图可以有许多棵不同的生成树（2）

31、所有生成树具有以下共同特点：）所有生成树具有以下共同特点：生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图生成树是图的极小连通子图 一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边 生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路 含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树生成树48V1V2V4V5V3V7V6V8例例深度遍历：深度遍历：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7

32、V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8V1V2V4V5V3V7V6V8广度遍历：广度遍历：V1 V2 V3 V4 V5 V6 V7 V8深度优先生成树深度优先生成树广度优先生成树广度优先生成树49例例ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林50问题提出问题提出：要在要在n个城市间建立通信联络网，顶点表示城市，权表示城市间建立个城市间建立通信联络网，顶点表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所

33、需花费的总代价）最小。之和（即建立该通信网所需花费的总代价）最小。问题分析问题分析：n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路条线路n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路条线路问题转化为：问题转化为：如何在可能的线路中选择如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。且总耗费（各边权值之和）最小。1654327131791812752410最小生成树最小生成树51方法一：普里姆方法一：普里姆(Prim)算法算法算法思想算法思想：设：设N=(V,E)是连通网，是连通网，T

34、E是是N上最小生成树中边上最小生成树中边的集合。的集合。(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例例1654326513566425131163141643142116432142516543214

35、253从从V1开始构造，即开始构造，即U=V153struct VertexType adjvex;/U集合中的顶点序号集合中的顶点序号 VRType lowcost;/和顶点集和顶点集U中顶点相连中顶点相连接的最小代价接的最小代价 closedgeMAX_VERTEX_NUM;设置一个辅助数组，对当前设置一个辅助数组，对当前VU集中的每个顶点，集中的每个顶点，记录和顶点集记录和顶点集U中顶点相连接的代价最小的边：中顶点相连接的代价最小的边：54abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5UV-Uab,c

36、,d,e,f,ga,eb,c,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表示相邻否；对带权图，则为权值类型。表示相邻否；对带权图，则为权值类型

37、。InfoType*info;/该弧相关信息的指针该弧相关信息的指针 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /图的定义图的定义VertexType vexsMAX_VERTEX_NUM;/顶点信息顶点信息AdjMatrix arcs;/表示顶点之间关系的二维数组表示顶点之间关系的二维数组int vexnum,arcnum;/图的当前顶点数和弧图的当前顶点数和弧(边边)数数GraphKind kind;/图的种类标志图的种类标志 MGraph;图的邻接矩阵存储表示的图的邻接矩阵存储表示的C语言描述语言描述56void MiniS

38、panTree_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;j;+j)/for(j=0;j;+j)/辅助数组初始化辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/closedgek.lowc

39、ost=0;/初始，初始，U Uuu for(i=1;i;+i)for(i=1;i;+i)k=minimum(closedge);k=minimum(closedge);/求出加入生成树的下一个顶点求出加入生成树的下一个顶点(k)(k)printf(closedgek.adjvex,G.vexsk);printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边输出生成树上一条边 closedgek.lowcost=0;closedgek.lowcost=0;/第第k k顶点并入顶点并入U U集集 for(j=0;j;+j)for(j=0;j;+j)/修改修改close

40、dgeclosedge数组数组 if(G.arcskj.adj closedgej.lowcost)if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;closedgej=G.vexsk,G.arcskj.adj;57165432651356642516543212345方法二：克鲁斯卡尔方法二：克鲁斯卡尔(Kruskal)算法算法算法思想：设连通网算法思想：设连通网N=(V,E)，令最小生成树令最小生成树（1）初始状态为只有）初始状态为只有n个顶点而无边的非连通图个顶点而无边的非连通图T=(V,)，每个顶点自成一个

41、连通分量；每个顶点自成一个连通分量；（2）在）在E中选取代价最小的边，若该边依附的顶点落在中选取代价最小的边，若该边依附的顶点落在T中不中不同的连通分量上，则将此边加入到同的连通分量上，则将此边加入到T中；否则，舍去此边，选中；否则，舍去此边，选取下一条代价最小的边；取下一条代价最小的边；（3）依此类推，直至）依此类推，直至T中所有顶点都在同一连通分量上为止。中所有顶点都在同一连通分量上为止。58（0）用顶点数组和边数组存放顶点和边信息）用顶点数组和边数组存放顶点和边信息（1）初始时，令每个顶点的）初始时，令每个顶点的jihe互不相同；每个边的互不相同；每个边的flag为为0（2）选出权值最小

42、且）选出权值最小且flag为为0的边的边（3）若该边依附的两个顶点的）若该边依附的两个顶点的jihe 值不同，即非连通，则令值不同，即非连通，则令 该边的该边的flag=1,选中该边；再令该边依附的两顶点的选中该边；再令该边依附的两顶点的jihe 以及两集合中所有顶点的以及两集合中所有顶点的jihe 相同相同 若该边依附的两个顶点的若该边依附的两个顶点的jihe 值相同，即连通，则令该值相同，即连通，则令该 边的边的flag=2,即舍去该边即舍去该边（4）重复上述步骤，直到选出）重复上述步骤，直到选出n-1条边为止条边为止 顶点结点：顶点结点：typedef struct int data;/

43、顶点信息顶点信息 int jihe;VEX;边结点：边结点：typedef struct int vexh,vext;/边依附的两顶点边依附的两顶点 int weight;/边的权值边的权值 int flag;/标志域标志域EDGE;算法实现算法实现59例例1654326513566425datajihe124536124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222算法描述算法描述260普里姆算法普里姆算法克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O

44、(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围两种算法的比较61问题提出问题提出：学生选修课程问题学生选修课程问题顶点表示课程，有向弧表示先决条件，若课程顶点表示课程，有向弧表示先决条件，若课程i是课程是课程j的先决条件，则图中有弧的先决条件，则图中有弧，学生应按怎样的顺序，学生应按怎样的顺序学习这些课程，才能无矛盾、顺利地完成学业，这就牵学习这些课程，才能无矛盾、顺利地完成学业，这就牵涉到涉到拓扑排序拓扑排序。拓扑排序拓扑排序62定义定义AOV网网：用顶点表示活动，用弧表示活动间优先关系：用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网的有向图

45、称为顶点表示活动的网(Activity On Vertex network)，简称简称AOV网。网。若若是图中有向边，则是图中有向边，则vi是是vj的的直接前驱直接前驱；vj是是vi的的直接后继。直接后继。AOV网中不允许有回路，否则意味着某项活动以自己网中不允许有回路，否则意味着某项活动以自己为先决条件。为先决条件。拓扑排序拓扑排序：把：把AOV网络中各顶点按照它们相互之间的网络中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。优先关系排列成一个线性序列的过程。检测检测AOV网中是否存在环方法：对有向图构造其顶点网中是否存在环方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都

46、在它的拓扑有序序的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该列中，则该AOV网必定不存在环。网必定不存在环。63拓扑排序的方法拓扑排序的方法（1）在有向图中选一个）在有向图中选一个没有前驱的顶点没有前驱的顶点且输出之；且输出之；（2）从图中）从图中删除删除该顶点和所有以它为尾的弧；该顶点和所有以它为尾的弧；（3）重复上述两步，直至全部顶点均已输出；或）重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止者当图中不存在无前驱的顶点为止64课程代号课程代号 课程名称课程名称 先修棵先修棵C1C2C3C4C5C6C7C8C9C10C11C12无无C1C1,C2C1C3,

47、C4C11C3.C5C3,C6无无C9C9C1,C9,C10程序设计基础离散数学数据结构汇编语言语言的设计和分析计算机原理编译原理操作系统高等数学线性代数普通物理数值分析C1C2C3C4C5C6C7C8C9C10C11C12拓扑序列：拓扑序列：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和

48、所有以它为尾和所有以它为尾的弧。的弧。66C2C3C4C5C6C7C8C9C10C11C12C3C4C5C6C7C8C9C10C11C12（2）选择没有前驱的顶点）选择没有前驱的顶点C2，删除删除C2和所有以它为和所有以它为尾的弧。尾的弧。拓扑序列：拓扑序列：C1-C2（3）选择没有前驱的顶）选择没有前驱的顶点点C3，删除删除C3和所有以和所有以它为尾的弧。它为尾的弧。拓扑序列：拓扑序列：C1-C2-C367C4C5C6C7C8C9C10C11C12C5C6C7C8C9C10C11C12（4）选择没有前驱的顶点）选择没有前驱的顶点C4，删除删除C4和所有以它为和所有以它为尾的弧。尾的弧。拓扑序

49、列：拓扑序列：C1-C2-C3-C4（5）选择没有前驱的顶点）选择没有前驱的顶点C5，删除删除C5和所有以它为和所有以它为尾的弧。尾的弧。拓扑序列：拓扑序列：C1-C2-C3-C4C568C6C8C11C12拓扑序列：拓扑序列：C1-C2-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拓扑序列：拓

50、扑序列：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-C5-C7-C9-C10-C11-C6-C12-C8（12）70那么如何进行拓扑排序？步骤如下：那么如何进行拓扑排序？步骤如下：（1）在在AOV网中选择一个没有前驱的顶点并输出；网中选择一个没有前驱的顶点并输出；（2）从从AOV网中删除该顶点以及从它出发的弧；网中删除该顶点以及从它出发的弧；重复以上两步直至重复以上两步直至AOV网变空（即已输出所有顶点）网变空（即