带边标记的DFS算法及其正确性_第1页
带边标记的DFS算法及其正确性_第2页
带边标记的DFS算法及其正确性_第3页
带边标记的DFS算法及其正确性_第4页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

1、带边标记的DFS算法及其正确性171860017 桑百惠DFS算法 深度优先搜索，顾名思义是以深度作为搜索策略的一种搜索算法：只要可能，就尽量在图中“深入”。（1）深度优先搜索总是对最近才发现的结点v所连接的出发边进行探索，直到该节点的所有出发边都被发现为止。（2）一旦结点v的所有出发边都被发现，搜索则“回溯”到v的前驱结点（v是经过该结点才被发现的），来搜索该前驱结点的出发边。（3）该过程一直持续到从源结点可以达到的所有结点都被发现为止。如果还存在尚未发现的结点，则深度优先搜索将从这些未被发现的结点中任选一个作为新的源结点，并重复同样的搜索过程。DFS算法 在对已经被发现的结点u的邻接链表进

2、行扫描时，每当发现一个结点v，就进行记录，将v 的前驱设为u 由于可能从多个源结点进行搜索，所以深度优先搜索的前驱子图可能由多棵树组成 用黑白灰三种颜色表示访问的状态，v.d表示v第一次被发现的时间，v.f表示完成对v的邻接链表扫描的时间DFS实现举例DFS的边的一些性质关于边类型的判定(无向图) 链接两层搜索的都是树边，即灰点和白点之间的边都为树边，否则是后向边 在四、五行之间添加V=tree edge算法正确性 通过DFS正确性可证明对所有边，和点都会进行搜索 根据之前的定理，在深度优先搜索的时候，每条边不是树边就是后向边。 根据定义，当一个点为灰色，另一个点为白色，这条边即为发现白色点的边，即为树边，否则为后向边。关于边类型的判定（有向图） 当u为灰色，v为白色，且（u,v）为发现v的边（u,v）为一条树边 当u为灰色，v为白色，u.dv.d (v,u)为后向边 当u为灰色，v为黑色且u.dv.d 则(u,v)为前向边 当u

人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

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

最新文档

评论

0/150

提交评论