数据结构10-11-12图_副本.ppt

数据结构课程的内容 第7章 图 7.1 图的基本术语 例：判断下列4种图形各属什么类型？ 证明： 稀疏图：稠密图： 带权图： 邻接点： 简单路径： 图的抽象数据类型 7.2 图的存储结构 图的特点： 1. 邻接矩阵（数组）表示法 例2 ：有向图的邻接矩阵如何表示？ 例3 ： 有权图（即网络）的邻接矩阵如何表示？ 图的邻接矩阵在机内如何表示？ （参见教材P161） 例：用邻接矩阵生成无向网的算法（参见教材P162） 2. 邻接表（链式）表示法 例1：无向图的邻接表如何表示？ 例3：已知某网的邻接（出边）表，请画出该网络。 邻接表存储法的特点： 讨论：邻接表与邻接矩阵有什么异同之处？ 图的邻接表在机内如何表示？ （参见教材P163） 7.3 图的遍历 一、深度优先有哪些信誉好的足球投注网站( DFS ) 深度优先有哪些信誉好的足球投注网站（遍历）步骤： 讨论1：计算机如何实现DFS？ 讨论2： DFS算法如何编程？ 讨论3：在图的邻接表中如何进行DFS？ 讨论4： 邻接表的DFS算法如何编程？ DFS 算法效率分析: 二、广度优先有哪些信誉好的足球投注网站( BFS ) 广度优先有哪些信誉好的足球投注网站（遍历）步骤： 讨论1：计算机如何实现BFS？ 讨论2： BFS算法如何编程？ BFS 算法效率分析: 7.4 图的其他运算 1.求图的生成树（或生成森林） 例1 ：画出下图的生成树 例2：画出下图的生成森林（或极小连通子图） 2. 求最小生成树 典型用途： 讨论：如何求得最小生成树？ 克鲁斯卡尔（Kruskal）算法: 计算机内怎样实现Kruskal算法？ 思考：计算机怎样根据邻接表来实现Kruskal算法？ 普利姆（Prim）算法示例： 归并顶点 普利姆（Prim）算法说明： 详细过程： 计算机内怎样实现Prim（普里姆）算法？ 具体示例： Prim算法流程 普利姆（Prim）算法： 例：用普里姆算法构造最小生成树的过程 3. 求最短路径 一、单源最短路径 (Dijkstra算法) 例2： Dijkstra（迪杰斯特拉）算法 算法描述： 例3： 算法的C语言程序见教材P189； 对应流程图见下页 算法流程： 二、所有顶点之间的最短路径 问题的提法： 已知一个各边权值均大于0的带权有向图，对每一对顶点 vi ? vj，希望求出vi 与vj之间的最短路径和最短路径长度。 7.5 图的应用(自学) 第7章小结 （3）对于所有不在S中的终点w，若 dist[u]+ A[u,w] dist[w] 则修改dist[w]为： dist[w]＝ dist[u]+ A[u,w] （4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。 算法的C语言程序见教材P189 用（v0, u, w）替换（v0, w） （2）选择u，使得 dist[u]＝min{dist[w] | w∈V-S } //u = min（v0,vi） S = S∪{u} vj v5 v4 v3 v2 v1 从v0到各终点的dist值和最短路径 终点 dist[w] v2到v4的长度=∞30 v2到v5的长度=∞100 S之外的当前最短路径之顶点 60 {v0,v2,v3} 50 {v0,v4,v3} 30 {v0,v4} 90 {v0,v4, v5} 60 {v0,v4,v3,v5} 5 5 4 0 3 1 2 100 60 30 10 10 20 50 s {v0,v2} {v0 ,v2 ,v4} {v0 ,v2 ,v4 ,v3} {v0 ,v2 ,v4 ,v3 ,v5} 10 {v0,v2} ∞ 30 {v0,v4} 100 {v0, v5} ∞ ∞ ∞ ∞ v2 v4 v3 v5 100 {v0, v5} 0 1 2 3 4 5 Void ShortPath_DIJ(Mgraph G, int v0, PathMatrix P, ShortPathTable D){ for(v=0; vG.vexnum; ++v){ Final[v]=false;D[v]= G.arcs[v0][v]; for(w=0;w G.vexnum;++w) P[v][w]= false; //设空路径 if(D[v]INFINITY){P[v][v0]=true; P[v][v]= true; } } //for D[v0]=0; final[v0]=true; For(i=1;iG.vexnum;++i){……} } i=G.vexnum 初始化过程; (i=1;) End N Y w G.vexnum min = INFINTY; (w=0;) w G.vexnum N Y