数据结构 邓欣-ch7-图.pptVIP

* 分别使用Prim算法和Kruskal算法给出： 从v1顶点出发的最小生成树 v1 v3 v6 v7 v8 v4 v5 v2 5 3 2 7 6 9 4 1 3 6 练习 * 分别使用Prim算法和Kruskal算法给出： 从v1顶点出发的最小生成树 v1 v3 v6 v7 v8 v4 v5 v2 5 3 2 6 4 1 3 1 2 3 4 5 6 7 使用Kruskal算法 v1 v3 v6 v7 v8 v4 v5 v2 5 3 2 6 4 1 3 1 2 3 4 5 6 7 使用Prim算法 有向无环图及其应用 拓扑排序 关键路径 有向无环图 无环的有向图，或称DAG（directed acycline graph）图 是描述工程或系统的进行过程的有效工具，如工程施工图，生产流程图，课程安排图，数据流图等 有向树、DAG图与有向图的区别 有向树中无环且只有n-1条弧 DAG图是无环的有向图 有向无环图及其应用 有向树 DAG图 有向图 有向无环图的应用 常见的工程问题或系统问题，如: 工程或系统能否顺利完成 ---- 拓扑排序 估算整个工程完成所必需的最短时间 ---- 关键路径 有向无环图及其应用 AOV(Activity on Vertex)网 用顶点表示活动，用弧表示活动间的优先(次序)关系的有向无环图 在AOV网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱，j是i的后继 在AOV网中，i, j是网中一条弧，则i是j的直接前驱，j是i的直接后继 AOV网 拓扑排序操作 生成一个拓扑有序序列，该序列满足条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前 拓扑排序的实际意义 有向图G中的每一条弧表示顶点之间的次序关系，在客观事件中拓扑排序用于寻找活动的执行(处理)顺序 拓扑排序 给定有向图 拓扑排序的方法 1）在有向图中选一个没有前驱(入度为0)的顶点且输出之 2）从图中删除该顶点和所有以它为尾的弧(出边) 重复上述两步，直至全部顶点均已输出，或当前图中不存在无前驱的顶点为止。(前一种情况表示拓扑排序成功，而后一种情况说明有向图中存在环) 拓扑排序 如表示课程之间优先关系的有向图： c1 c4 c2 c3 c5 c7 c9 c10 c11 c6 c8 c12 拓扑有序序列： c1, c2, c3, c4, c5, c7, c9, c10, c11, c6, c12, c8 或 c1, c4, c2, c3, c5, c7, c9, c10, c11, c12, c6, c8 或 c9, c10, c11, c6, c1, c12, c4, c2, c3, c5, c7, c8 或 … … 如AOV网 v1 v2 v4 v3 v6 v5 拓扑有序序列： v1, v6, v4, v3, v2, v5 或 v6, v1, v4, v3, v2, v5 或 v6, v1, v4, v3, v5, v2 或 … … v4 v2 v5 v1 v3 如： 该图无法进行拓扑排序，因为图中有环 一个有向无环网的拓扑序列不一定唯一 有环网不能进行拓扑排序 拓扑排序 拓扑排序算法 采用邻接表存储有向图 且在头结点中增加一用于存放顶点入度的数组indegree 为了避免重复检测入度为0的顶点，另设一栈暂存所有入度为0的顶点 拓扑排序 Status TopologicalSort(ALGraph G) { //有向图G采用邻接表存储结构 //若G无回路，则输出G的顶点的一个拓扑序列并返回OK, 否则ERROR FindIndgree(G, indegree); //对各顶点求入度indegree[0..vexnum-1] InitStack(S); for (i = 0; i G.vexnum; ++i) if (!indegree[i]) push(S, i); //若入度为0则进栈 count = o; //对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf(i, G.vertices[i].data); ++count; //输出i号顶点并计数 for (p = G.vertices[i].firstarc; p; p= p-nextarc) { k = p-adjvex; //对i号顶点的每个邻接点的入度减1 if (!(--indegree[k])) push(S, k); //若入度减为0，则入栈