图的遍历和连通性.ppt_第1页
图的遍历和连通性.ppt_第2页
图的遍历和连通性.ppt_第3页
图的遍历和连通性.ppt_第4页
图的遍历和连通性.ppt_第5页
已阅读5页，还剩20页未读， 继续免费阅读

下载本文档

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

文档简介

1、1，7.1基本术语7.2存储结构7.3图的遍历7.4图的连通性7.5图的应用，第7章图2，7.3遍历，遍历：从给定连通图中的一个顶点开始，沿着一些边访问图中的所有顶点，并使每个顶点只被访问一次，称为图的遍历，这是图的基本操作。遍历：寻找每个顶点的相邻点的过程。图的特征：图中可能有一个循环，图中的任何一个顶点都可以与其他顶点通信。访问一个顶点后，它可能会沿着某些边返回到曾经访问过的顶点。解决方案：可以设置一个辅助阵列访问n来标记每个访问的顶点。它的初始状态是假的。在图的遍历过程中，一旦一个顶点I被访问，它会立即将被访问的I更改为true，以防止它被重复访问。如何避免重复访问？深度优先搜索和广度优

2、先搜索，常用于图的遍历：1，深度优先搜索，深度优先搜索，基本思想：类似于树的第一根遍历过程。1.连通图的深度优先搜索遍历，步骤：访问起点V；从V的未访问的相邻点开始依次遍历深度图，直到图中与V有路径通信的所有顶点都被访问。4，v1，DFS结果：示例1:V2，v4，V8，V5，v3，V6，V7，起点，应退回到V8，因为v2已被标记，使DFS无效(图G，int v) /从顶点v开始，以深度优先的方式遍历gvisis。(w=FirstAdjVex(G，v)；w！=0；w=NextAdjVex(G，v，w) if(！访问(w) DFS(G，w)；/递归调用DFS /DFS，5到尚未被访问的V的相邻顶点

3、W。对于无向图，该算法可以遍历V顶点所在连通分支中的所有顶点，但不能遍历与V顶点不在同一连通分支中的所有顶点；对于有向图，它可以遍历起始顶点V可以到达的所有顶点。如果您想要遍历图中的所有顶点，您需要在上述深度优先遍历算法的基础上添加对每个顶点的访问状态的检测。2.不连通图的深度优先搜索遍历，步骤：访问起点V和图中与V有路径通信的所有顶点。如果图中仍有未被访问的顶点，则以该顶点为起点，执行深度优先搜索遍历。重复上述过程，直到访问完所有顶点。6，a，b，c，h，d，e，k，f，g，f f f f f f f f f f，t，t，t，t，t，t，t，0 1 2 3 4 5 6 7 8，8，1，2，3，4，5，6，7，0，空

人人文库> 全部分类> 教育资料 > 课设设计

温馨提示

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

最新文档

评论

0/150

提交评论