深度优先搜索 DFS

深度优先搜索 DFS1、基本思想2、算法实现3、单点路径问题4、连通分量问题5、检测环与双色问题6、总结1、基本思想在搜索一幅图时,只需要用一个递归来遍历所有顶点。在访问其中一个顶点时:-将它标记为已访问-递归访问它的所

1、基本思想

在搜索一幅图时,只需要用一个递归来遍历所有顶点。在访问其中一个顶点时:
– 将它标记为已访问
– 递归访问它的所有未标记的邻居顶点

DFS只会访问与起点s连通的所有顶点(而不会访问其他顶点)。如果图是连通的,则所有顶点都会被访问到。
DFS中每条边都会被访问两次,且在第二次时总会发现这个顶点已经被标记过了。

2、算法实现

/*单点连通性*/
public class DepthFirstSearch{
    private boolen[] marked;    //使用一个boolean数组来记录和起点s连通的所有顶点
    private int count;          //与起点s连通的顶点数目

    public DepthFirstSearch(Graph G, int s){
        marked = new boolen[G.V()];
        dfs(G, s);    
    }

    private void dfs(Graph G, int v){
        count++;
        marked[v] = true;
        for (int w : G.adj(v)){
            if (!marked[w]){
                dfs(G, w);
            }
        }
    }

    public boolen marked(int v){ return marked[v]; }
    public int count(){ return count; }
}

下图显示算法轨迹,起点为顶点0。 1、因为顶点2是0的邻接表的第一个元素且没有被标记过,dfs()标记该位置并且访问顶点2。

2、接下来,顶点0是2的邻接表的第一个元素且已经被标记过了,因此dfs()跳过了它。然后,顶点1是2的邻接表的第二个元素且没有被标记,调用dfs()来标记并访问顶点1。

3、对于顶点1的访问和前面的有所不同:因为它的邻接表中所有顶点(0和2)都已经被标记过,因此不需要再进行递归,方法从dfs(1)返回,下一条被检查的边时2-3,因此调用dfs()标记并访问顶点3.

。。。。后续同理
这里写图片描述
深度优先搜索可处理问题:
连通性。可以回答 “两个给定的顶点是否连通?” 或者 “找出图中所有连通分量” 等类似问题
单点路径。可以回答 “从s到目的顶点v是否存在一条路径?如果有找出这条路径” 等类似问题

3、单点路径问题

图处理算法的设计模式:将图的表示实现分离开来。为每个处理图的任务创建一个相应的操作类,用例可以创建相应的对象来完成任务。
典型的用例程序会构造一幅图,将 图Graph 传递给实现了某个处理算法的类(作为其构造函数的参数),然后调用方法来获取图的各种性质。

根据上述设计模式,单点路径问题的API如下:
构造函数 Paths() 接受一个图和 起点s 作为参数,计算 s 到 与s连通的所有顶点 之间的路径。
在为 起点s 创建了 Paths对象 后,用例可以调用 pathTo() 方法 来遍历从s到v的路径上的所有顶点。
这里写图片描述

下述算法基于深度优先搜索实现了Paths操作类。它扩展了DepthFirstSearch,添加了一个实例变量 edgeTo[] 整型数组。根据这个数组可以回溯找到从每个与s连通的顶点回到s的路径。它会记住每个顶点到起点的路径。

/* 使用深度优先搜索查找图中的路径*/
public class DepthFirstPaths {
    private boolean[] marked;  //顶点是否以被标记
    private int[] edgeTo;      //从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;       //起点

    //找出所有起点为s的路径
    public DepthFirstPaths(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;  //v-w是从s到达w最后一条经过的边
                dfs(G, w);
            }
        }
    }

    //是否存在从起点s到v的路径
    public boolean hasPathTo(int v){
        return marked[v];
    }

    //起点s到v的路径,如果不存在则返回null
    public Iterable<Integer> PathTo(int v){
        if (!hasPathTo(v))  return null;
        Stack<Integer> path = new Stack<Integer>();
        for (int x=v; x!=s; x=edgeTo[x])
            path.push(x);
        path.push(s);
        return path;
    }
}

下图是深度优先搜索算法的一个简单例子的追踪。
黑色粗线条表示深度优先搜索中,所有顶点到原点0的路径,他是通过 edgeTo[] 这个变量记录的。可以看出, edgeTo[]数组 其实是一颗树,树根即是原点,每个子节点到树根的路径即是从原点到该子节点的路径。
这里写图片描述
这里写图片描述 这里写图片描述

4、连通分量问题

DFS在单点路径后的下一个直接应用就是找出一幅图的所有连通分量,它能将所有顶点切分为等价类(连通分量)。

对于这个任务定义API如下:
这里写图片描述

构造函数 CC() 中使用 marked[]数组 来寻找一个顶点作为每个连通分量中 深度优先搜索dfs() 的起点。

递归的 dfs() 第一次调用的参数是顶点s——它会标记所有与s连通的顶点。然后构造函数的 for()循环 会继续查找每个未被标记的顶点并递归调用 dfs() 来标记并区分所有和它连通的顶点,如此重复直到所有的顶点都被标记并区分。

使用由顶点索引的数组 id[]。如果v属于第i个连通分量,则id[v]的值为i

/*使用DFS找出图中的所有连通分量*/
public class CC
{
    private boolean[] marked;
    private int[] id;
    private int count;

    //构造函数找出图中的所有连通分量
    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s])
            {
                dfs(G, s);
                count++;
            }
    }

    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }

    public boolean connected(int v, int w) { return id[v] == id[w]; }  //v 和 W 是否连通

    public int id(int v) { return id[v]; }

    public int count() { return count; }  //连通分量数
}

测试用例如下:
它能从标准输入中读取一幅图并打印其中的连通分量,每行表示一个连通分量。
这里写图片描述 这里写图片描述

5、检测环与双色问题

检测环:给定的图是无环图吗?
双色问题:等价于 “这是二分图吗?”

/* 检测G是否是无环图 */
public class Cycle
{
    private boolean[] marked;
    private boolean hasCycle;
    public Cycle(Graph G){
        marked = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s])
                dfs(G, s, s);
    }
    private void dfs(Graph G, int v, int u) {  //定义u为递归的上一个顶点
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w, v);
            else if (w != u) hasCycle = true;   //
    }
    public boolean hasCycle(){ return hasCycle; }
}
/* 检测G是否是二分图 (双色问题) */
public class TwoColor
{
    private boolean[] marked;
    private boolean[] color;
    private boolean isTwoColorable = true;
    public TwoColor(Graph G)
    {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for (int s = 0; s < G.V(); s++)
            if (!marked[s]) dfs(G, s);
    }
    private void dfs(Graph G, int v)
    {
        marked[v] = true;
        for (int w : G.adj(v))
            if (!marked[w]){
                color[w] = !color[v];
                dfs(G, w);
            }
            else if (color[w] == color[v]) isTwoColorable = false;
    }
    public boolean isBipartite(){ return isTwoColorable; }
}

6、总结

本章总结:
– 图的术语
– 图的表示方法
– 图处理相关的类的设计模式。其实现算法通过在相关类的构造函数中对图进行预处理,构造所需的数据结构来支持用例对图性质的查询
– 深度优先搜索、广度优先搜索

下面总结了已经学习过的所有图算法的实现:
这里写图片描述

今天的文章深度优先搜索 DFS分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/17682.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注