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

  1. 1、本文档共71页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
数据结构课程的内容 第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

文档评论(0)

xiaofei2001128 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档