数据结构图@南京工程学院通信工程学院.ppt

* 方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次—— T(n)=O(n3) 方法二：弗洛伊德(Floyd)算法 算法思想：逐个顶点试探法(vi,vj) 求最短路径步骤 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧Vi,Vj，则对应元素为权值；否则为? 逐步试着在原直接路径中增加中间顶点（依次为v0,v1,…），若加入中间点后路径变短，则修改之；否则，维持原值 所有顶点试探完毕，算法结束 二、每一对顶点之间的最短路径 * 例 A C B 2 6 4 3 11 0 4 11 6 0 2 3 ? 0 初始： 路径： AB AC BA BC CA 0 4 6 6 0 2 3 7 0 加入B： 路径： AB ABC BA BC CA CAB 0 4 11 6 0 2 3 7 0 加入A： 路径： AB AC BA BC CA CAB 0 4 6 5 0 2 3 7 0 加入C： 路径： AB ABC BCA BC CA CAB 求每一对顶点之间的最短路径的示例： * 算法实现 图用邻接矩阵存储 length[][]存放最短路径长度 path[i][j]是从Vi到Vj的最短路径上Vj前一顶点序号 算法描述 例 1 3 2 2 6 4 3 11 初始： 0 4 11 6 0 2 3 ? 0 length= 0 1 1 2 0 2 3 0 0 path= 加入V1： 0 4 11 6 0 2 3 7 0 length= 0 1 1 2 0 2 3 1 0 path= 加入V2： 0 4 6 6 0 2 3 7 0 length= 0 1 2 2 0 2 3 1 0 path= 加入V3： 0 4 6 5 0 2 3 7 0 length= 0 1 2 3 0 2 3 1 0 path= 算法分析：T(n)=O(n3) 1给出如图所示的无向图G的邻接矩阵和邻接表两种存储结构。 作业 2. 假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。 3. 分别给出如图所示G图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站得到的顶点访问序列。 4. 应用prim算法求图所示带权连通图的最小生成树。 * 图 存储结构 遍 历 邻接矩阵 邻 接 表 十字链表 邻接多重表 深度优先有哪些信誉好的足球投注网站DFS 广度优先有哪些信誉好的足球投注网站DFS 无向图的应用 应用 图的连通分量 图的生成树 最小生成树 Prim算法 Kruskal算法 有向(无环)图的应用 最短路径 Dijkstra算法 Floyd算法 （利用DFS） 本章小结-体系结构图 (利用DFS和BFS) AOV网,AOE网 拓扑排序 关键路径 * 　1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 　2. 熟练掌握图的两种有哪些信誉好的足球投注网站路径的遍历：遍历的逻辑定义、深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。 3. 应用图的遍历算法求解各种简单路径问题。 　4. 理解教科书中讨论的各种图的算法。 本章小结 （续） * * 问：当E(G)为空时，图G存在否？ 答：还存在！但此时图G只有顶点而没有边。 * 证明： ①完全无向图有n(n-1)/2 条边。 证明：若是完全无向图，则顶点1必与所有其他顶点各有1条连线，即有n-1条边，顶点2有n-2条边，…，顶点n-1有1条边,顶点n有0条边. 总边数＝ n-1＋ n-2＋…＋1＋0=（n-1+0)n/2= n(n-1)/2 ② 完全有向图有n(n-1)条边。 证明：若是完全有向图，则顶点1必必与所有其他顶点各有2条连线，即有2(n-1)条边， 顶点2有2(n-2)条边，…，顶点n-1有2条边,顶点n有0条边. 总边数＝2( n-1＋ n-2＋…＋1＋0)=2(n-1+0)n/2= n(n-1) * 无向图中，顶点的度为与每个顶点相连的边数 有向图中，顶点的度分成入度与出度 入度：以该顶点为头的弧的数目 出度：以该顶点为尾的弧的数目 * * 　由于图结构中任意