数据结构 第七章-图2课件_第1页
数据结构 第七章-图2课件_第2页
数据结构 第七章-图2课件_第3页
数据结构 第七章-图2课件_第4页
数据结构 第七章-图2课件_第5页
已阅读5页，还剩94页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、第七章图表，图是多对多结构关系，每个要素可以有零个或更多的直接趋势。零个或多个直接后继。1，PPT学习通信，确定重点:图的两种遍历方法：定义遍历，深度优先搜索遍历，广度优先搜索遍历算法；图的遍历算法决定了图的连通性和图的生成树。用Prim、Kruskal算法求图的最小生成树；用Dijkstra算法求解单源最短路径问题。使用Floyd算法查找所有顶点之间的最短路径问题。使用AOV网络排序拓扑使用AOE网络查找关键路径问题手掌夹点:掌握图形的定义和术语。图表中的各种存储结构及其配置算法，以及解决实际问题的效率。2，PPT学习通信，7.3地物中的横向，7.3地物中的横向：从地物中的一个顶点开始访问地

2、物中的所有顶点，每个顶点仅访问一次。图形结构的遍历复杂性：(1)图形结构没有“自然”的第一个节点，图形的任何顶点都可以是第一个访问的节点(2)。由于非连接图形只能访问从一个顶点开始的连接组件中的所有顶点，因此，还必须考虑选择下一个起点以访问图形的其馀连接组件(3)。如果存在循环，然后访问顶点，则可以沿循环返回到该顶点。防止重复访问的方法(4)图结构中一个顶点与多个其他顶点相邻的方法，考虑访问这些顶点后如何选择下一个要访问的顶点的问题，3，PPT学习交流，图的遍历方法有深度优先遍历和宽度优先遍历。7.3.1深度优先搜索(1)从图中的顶点之一V0开始访问此顶点；(2)从V0未访问的相邻点开始，深度

3、首先通过图表，直到访问了图形中与V0关联的所有顶点。如果地物中仍有无法访问的顶点，请选择其他地物无法访问的顶点作为起点，然后重复此过程，直到地物中的所有顶点都被访问。4，PPT学习交流，如果图形的存储结构是相邻表，则访问相邻点的顺序不是唯一的，深度优先级也不是唯一的，将，V0，V1，V3，V4，V7，V2，V5，V6，图形G从v 0开始的深度优先级序列(将存储结构设置为相邻矩阵)visit(v)；/* v访问第二个顶点*/for (w=FirstAdjVex(G，v)；w；W=NextAdjVex(G，v，w)if(！Visitedw) DFS(G，w)；/* v尚未访问的相邻顶点w递归调用DFS*/，辅助阵列：int visitedMax _ Vertex _ Num访问标志数组，全局变量，最初所有组件为0，visitedv=1表示顶点v已访问。visited，深度优先遍历算法：7.3通过图，6，PPT学习交换，通过7.3图，在相邻表存储结构中深度优先搜索：v

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论