数据结构七-图.ppt

* 1。是否存在环 检查—个有向图是否存在环要比无向图复杂。对于连通的无向图来说，若深度优先遍历过程中又遇到已访问过的顶点，则必定存在环。 对于有向图来说，这条回边有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发进行遍历，在dfs(v)结束之前出现—条从顶点u到顶点v的回边。由于在生成树上v是u的子孙，则有向图中必定存在包含顶点v和u的环。 2。流程图问题 除最简单的情况之外，几乎所有的工程(project)都可分为若干个称做活动(activity)的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些些子工程完成之后。 对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。对应于有向图，即为进行拓扑排序和关键路径的操作。 * 本章小结 图是一种多对多的数据结构，每个元素可以有零个或多个直接前趋；零个或多个直接后继。 在图中存在两种关系：顶点之间的邻接关系和边与顶点间的关联关系。 图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表等。无论哪一种存储结构都要存储图中的顶点和顶点间的关系。 图的遍历方法有深度优先遍历和广度优先遍历两种，应用图的遍历可以判断图的连通性。 * 求生成树是为了在网络中连通n个顶点而选择最少的边（n－1），应用图的遍历可以求图的生成树。 求最小生成树是为了获得在网络中连通n个顶点的最低造价的方案，Prim算法的原理是每次向最小生成树中加顶点和边、Kruskal算法的原理是每次向最小生成树中加边。 单源最短路径问题是在网络中求从某顶点出发到达其他各点的最短路径，Dijkstra算法可以有效解决该问题。每对顶点间的最短路径问题可以由Floyd算法解决。 有向无环图包括AOV网和AOE网。利用AOV网可以进行拓扑排序，为项目中子任务分配可行进度安排。利用AOE网可求关键路径，估算完成项目的时间。 * * 考试题型 选择 ［待定］ 判断 填空 ［待定］ 简答题 编程题 1×10 * 题型示例 简答题： 队列的状态变化 由遍历序列恢复二叉树 构造哈夫曼树 画图的存储结构 求连通网的最小生成树 求单源最短路径 求拓扑排序 求关键路径 编程题：关于单链表的运算 * 对角线元素全为0。构造最小生成树的过程中，若顶点已包含在生成树里，就把其对应的对角线元素置为“1”；若边(vi,vj)已包含进生成树里，就把A[i,j]或A[j,i]位于下三角的一个置为负值 * 0 0 0 2 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 * 0 0 0 2 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p=NULL 3 3 2 1 0 4 top 2 输出序列： 5 0 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 4 ^ 输出序列： 5 0 2 3 3 2 1 0 4 top 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^ ^ ^ vex next 2 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p 3 3 2 1 0 4 top 输出序列： 5 0 2 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^ ^ ^ vex next 1 ^ 1 4 ^ 1 3 0 0 1 2 3 4 5 ^ p 3 3 2 1 0 4 top 输出序列： 5 0 2 7.6 有向无环图及其应用 * 0 0 0 1 in link 4 4 3 2 ^