深度优先搜索

栏目: 数据库 · 发布时间: 6年前

内容简介:要搜索一幅图,用一个递归方法来遍历所有顶点。在访问其中一个顶点时:给定一幅图,回答“两个给定的顶点是否连通?”或者“图中有多少个连通子图?”给定一幅图和一个起点

要搜索一幅图,用一个递归方法来遍历所有顶点。在访问其中一个顶点时:

  • 将它标记为已访问
  • 将它添加到路径当中去
  • 递归地访问它的所有没有被标记过的邻居顶点

相关问题

连通性

给定一幅图,回答“两个给定的顶点是否连通?”或者“图中有多少个连通子图?”

单点路径

给定一幅图和一个起点 s ,回答“从 s 到给定目的顶点 v 是否存在一条路径?如果有,找出这条路径。”

搜索轨迹

深度优先搜索

深度优先搜索

  1. 如图所示,起点为 0
  2. 因为顶点 20 的邻接表第一个元素且没被标记过, dfs() 递归标记并访问 2
  3. 对于顶点 2 ,顶点 0 为其邻接表第一个元素,但是它已经被标记,所以跳过。所以 dfs() 标记并访问邻接表中第二个顶点 1
  4. 对于顶点 1 ,其邻接表中的所有顶点已经都被标记过,因此不再需要递归,方法从 dfs(1) 中返回。接下来访问的是 2 的邻接表中 1 后面的顶点 3
  5. 对于顶点 3 ,顶点 53 的邻接表中未被标记的第一个元素,于是标记并访问顶点 5
  6. 对于顶点 5 ,邻接表中顶点都已经标记过了,于是不再递归
  7. 顶点 43 的邻接表中下一个没被标记的顶点,于是标记并访问 4 .这是最后一个需要被标记的顶点
  8. dfs() 检查 4320 的邻接表,因为都被标记过所以不再进行递归

寻找路径

edgeTo[] 数组用于记录从起点 s 到目标点 v 路径中 v 的前一个顶点。

如对于一条路径 s-a-b-c-vedgeTo[v]=c

这样对于 sv ,迭代获取 edgeTo[] 中的顶点就可以得到路径。

路径记录详细过程如下图所示:

深度优先搜索

代码

public class DFS {
    private boolean[] marked;   //此顶点上是否调用过dfs()
    private int[] edgeTo;   //从起点到一个已知路径上最后一个顶点
    private int s;  //起点
    public DFS(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }
    private void dfs(Graph G, int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))  return null;
        Stack<Integer> pathReverse = new Stack<>();
        for (int x = v; x != s; x = edgeTo[x])
            pathReverse.push(x);
        pathReverse.push(s);
        Queue<Integer> path = new LinkedList<>();
        while (!pathReverse.isEmpty())
            path.offer(pathReverse.pop());
        return path;
    }
}

以上所述就是小编给大家介绍的《深度优先搜索》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

影响力

影响力

[美] 罗伯特·西奥迪尼 / 陈叙 / 中国人民大学出版社 / 2006-5 / 45.00元

政治家运用影响力来赢得选举,商人运用影响力来兜售商品,推销员运用影响力诱惑你乖乖地把金钱捧上。即使你的朋友和家人,不知不觉之间,也会把影响力用到你的身上。但到底是为什么,当一个要求用不同的方式提出来时,你的反应就会从负面抵抗变成积极合作呢? 在这本书中,心理学家罗伯特·B·西奥迪尼博士为我们解释了为什么有些人极具说服力,而我们总是容易上当受骗。隐藏在冲动地顺从他人行为背后的6大心理秘笈,正是......一起来看看 《影响力》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

SHA 加密
SHA 加密

SHA 加密工具

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具