数据结构南开大学.ppt

数据结构 第7章 图 - 2 第7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路经 7.4 图的连通性问题 7.4.1 无向图的连同分量和生成树 7.4.2 有向图的强连同分量 7.4.3 最小生成树 7.4.4 关节点和重连同分量 7.4.1 无向图的连同分量和生成树 7.4.1 无向图的连同分量和生成树 7.4.1 无向图的连同分量和生成树 7.4.2 有向图的强连同分量 深度优先搜索是求有向图的强连同分量的一个有效方法。 7.4.3 最小生成树 最小代价生成树（简称：最小生成树） Minimum Cost Spanning Tree 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.3 最小生成树 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.4.4 关节点和重连同分量 7.5 有向无环图及其应用 何为有向无环图（DAG 图）Directed Acyclic Graph 7.5 有向无环图及其应用 用途：描述工程项目或系统进行的工具 7.5.1拓扑排序 拓扑排序（Topological Sort）由某个集合上的一个偏序得到该集合上的一个全序。 偏序(Partial Order)：若集合 X 上的关系 R 是传递的、自反的、反对称的，则称 R 是集合 X 上的偏序关系。 全序(Total Order)：若关系 R 是集合 X 上的偏序关系，如果对于每个 x, y 属于 X，必有 x R y 或 y R x ，则称 R 是集合 X 上的全序关系。 7.5.1拓扑排序 拓扑排序：由某个集合上的一个偏序关系通过人为地加上一些关系得到该集合上的一个全序。 用途：描述工程项目或系统进行的次序AOV 网络：定义结点为活动，有向边的指向表示活动执行的次序。 7.5.1拓扑排序 实例：下述集合 M 代表课程的集合，其中，1代表数学， 2代表程序设计，3代表离散数学，4代表汇编程序设计，5代表数据结构，6代表结构程序设计, 7代表编译原理。 关系 R 课程学习的先后关系，如数学必须在离散数学之前学习。要求排一张学习的先后次序表。 7.5.1拓扑排序 那么如何进行拓扑排序？步骤如下： （1） 在AOV网中选择一个没有前驱的顶点并输出； （2） 从AOV网中删除该顶点以及从它出发的弧； 重复以上两步直至AOV网变空（即已输出所有顶点）或者剩余子图中不存在没有前驱的顶点。后一种情况则说明该AOV网中含有向环。 7.5.1拓扑排序 实例：课程学习先后关系的排序。 7.5.1拓扑排序 算法（使用邻接表） 7.5.1拓扑排序 算法（使用邻接矩阵） 7.5.1拓扑排序 算法描述如下（使用邻接矩阵） 　　建有向图的邻接表并统计各顶点的入度； 　　InitStack(S); 　　　　　　　　　// 初始化S为空栈 　　将当前所有入度为零的顶点入栈; 　　m=0; 　　　　　　　　　　　　　// 以 m 记输出的顶点个数 　　while (!StackEmpty(S)) { 　　　// 尚有入度为零的顶点存在 　　　Pop(S,v); 　　　输出 v ; ++m; 　　　　　　// 输出入度为零的顶点，并计数 　　　w = FirstAdj(G,v);　　　　　　// w 为 v 的邻接点 　　　while (w0) {　　　　　　　// 将v 的所有邻接点的入度减1 inDegree[w]--; 　　　　　　// w 的入度减一 if( 0==inDegree[w]) Push(S,w); w = nextAdj(G,v,w);　　　　// 取 v 的下一个邻接点 　　　} // while w 　　} // while S 　　if (mn) printf(“图中有回路”); // 输出的顶点数不足图中顶点数 　　DestroyStack(S); 7.5.2 关键路径 关键路径: AOE 网络的应