《数据结构_最小生成树与拓扑排序_C》由会员分享，可在线阅读，更多相关《数据结构_最小生成树与拓扑排序_C（37页珍藏版）》请在金锄头文库上搜索。
1、第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径7.4 图的连通性问题1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法例：图及其生成树656 65513420对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。连通网最小生成树的意义？如何构造最小生成树？对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。连通网最小生成树的意义？如何构造最小生成树？最小生成树的MST性质：假设 N =（V,E）是一个连通网，U是顶点集 V 的一
2、个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中 u U，vV-U，则必存在一棵包含边（u,v）的最小生成树。656 655134207.4 图的连通性问题1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法3.普里姆（Prim）算法基本思想：(1)假设 G=(V,E) 是一个具有 n 个顶点的连通网络，T=(U，TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，U 和 TE 的初值均为空；(2)从 V 中任取一个顶点（假定为 V1），将此顶点并入 U中，此时最小生成树顶点集 U=V1；(3)从那些其中一个端点已在 U 中，另一端点
3、仍在 U 外的所有边中，找一条最短（即权值最小）的边，设该边为(Vi,Vj)，其中 ViU，VjV-U，并把该边和顶点 Vj分别并入 T 的边集 TE 和顶点集 U；(4)如此进行下去，每次往生成树里并入一个顶点和一条边，直到 n-1 次后，把所有 n 个顶点都并入生成树 T 的顶点集 U 中，此时 U=V，TE中包含有（n-1）条边；这样，T 就是最后得到的最小生成树。实现该算法需附设一个辅助数组closedge， 以记录从 U 到 V-U 具有最小代价的边。对每个 顶点 viV-U，在辅助数组中存在一个相应分量 closedgei-1(下标从0开始)，它包括两个域。 其中：lowcost存
4、储该边上的权。显然，closedgei-1.lowcost=Mincost(u，vi)|uU即vi到已生成子树的最短距离等于到U中所有 顶点中的最小边的权值。vex域存储该边依附的在U中的顶点。例：求下图最小生成树。假设开始顶点就选为顶点1，故有U=1，V-U=2，3，4，5，6(a )无向网64V1V2V4V36213V55V655 6(b) U=1 V-U=2,3,4,5,612345665153124561456(c) U=1,3 V-U=2,4,5,631 2456 4215 6(d) U=1,3,6 V- U=2,4,5312456421 56(e) U=1,3,6,4 V-U=2,
5、5(f) U=1,3,6,4,2 V-U=5124356421 53(g) U=1,3,6,4,2,5 V-U= 54213124356(a )无向网64V1V2V4V36213V55V655 6基于邻接矩阵的普里姆算法struct VertaxType adjvex; /顶点编号VRType lowcost; / =Mincost(u,vi|uU) closedgeMAX_VERTEX_NUM;Void MiniSpanTree_PRIM(MGraph G, VertexType u) k = LocateVex ( G, u ); / 顶点u为构造生成树的起始点,返回顶点u在图中的位置fo
6、r ( j=0; jnextarc)k=p-adjvex；/对i号顶点的每个邻接点入度减1if(！(-indegreek)Push(S，k);/若入度减为0，则入栈/for/whileif(countG.vexnum) return ERROR;/该有向图有回路else return OK；/TopologicalSort 分析：对有 n 个顶点和 e 条弧的有向图而言，建 立求各顶点的入度的时间复杂度为O(e)；建零入 度顶点栈的时间复杂度为O(n)；在拓扑排序过程 中，若有向图无环，则每个顶点进一次栈，出一 次栈，入度减1的操作在 WHILE语句中总共执行e 次，所以，总的时间复杂度为O(n+e)。拓扑排序的算法是下一讲讨论的求关键路径的 基础。
