乐趣区

关于java:图算法系列之深度优先搜索一

jiezi

前言

在上一篇中咱们把图通过邻接表数组示意进去了，这个数据结构将会做咱们实现图算法的根底，本篇咱们将一起开始学习图算法的第一个搜索算法 – 深度优先搜寻

搜寻 API 的定义

public class Search {Search(Graph graph, int s);

    boolean marked(int v);
    
    int count();}

在开始实现算法之前，咱们仍然先来定义搜寻的 API

  1. 构造方法提供了一个图对象，以及一个终点 s，须要找到与 s 连通的所有顶点
  2. marked 判断顶点 s 与 v 是否相邻
  3. count 返回与顶点 s 相连的总顶点数

深度优先搜寻

如果上图是一个迷宫，咱们须要从顶点 0 开始找到一条前途，假如咱们有一条有限长的绳子，和一支粉笔，那么能够这样思考找到前途：

  1. 先抉择一条通道走，在走的路上放上一根绳子
  2. 每遇到一个路口就用笔标记一下，持续抉择一条未走过的通道
  3. 当遇到一个曾经被标记的路口时就退回到上一个路口持续抉择一个未走过的通道
  4. 当回退的路口曾经没有路能够走的时候就在持续往后回退

这种形式绳子总能帮你找到一条前途，而标记不会让你反复走曾经走过的通道。

深度优先搜寻的实现思路就和走迷宫的形式一样；

public class DepthFirstSearch {private boolean marked[]; 
    private int count;

    public DepthFirstSearch(Graph graph, int s) {this.marked = new boolean[graph.V()];
        this.dfs(graph, s);
    }

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

    @Override
    public boolean marked(int v) {return marked[v];
    }

    @Override
    public int count() {return count;}
}

在搜寻一张图的时候，应用递归来遍历所有的顶点，在拜访其中一个顶点时：

  1. 标记它被曾经拜访
  2. 递归的拜访与之相连的所有邻接点

单元测试：
构建上面这张图，而后测试深度优先搜寻

@Test
public void test() {Graph graph = new Graph(8); // 构建一张图
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 5);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(4, 3);
    graph.addEdge(5, 3);
    
    graph.addEdge(6, 7); // 为了展现

    SeDepthFirstSearcharch search = new DepthFirstSearch(graph, 0);
    System.out.println(search.count());
    System.out.println(search.marked(6));
    System.out.println(search.marked(7));
    System.out.println(search.marked(2));
    System.out.println(search.marked(5));
}

寻找门路的 API

以上的递归算法只是一个开始，从下面的后果咱们能够看出，咱们只能判断出哪些顶点与终点 s 是连通的，无奈给出具体的门路进去；换句话说，咱们须要实现从顶点 s 到顶点 v 是否存在门路可达，如果存在请打印进去

public class Paths {Paths(Graph graph, int s);
    
    boolean hasPathTo(int v); // 判断出从 s ->v 是否存在门路
    
    Iterable<Integer> pathTo(int v); // 如果存在门路，返回门路
}

基于深度优先搜寻查找图中的可达门路

咱们仍然基于这张图来看，因为咱们须要找出可达的门路，所以咱们在进行搜寻的时候须要记录下图中的边，这里咱们应用的是一个数组 edgeTo[]，如果存在一条边是 v ->w，那么能够示意成 edgeTo[w]=v，在深度搜寻实现之后这个 edgeTo[]数组就是一颗由父链示意的一颗树
（父链树在之前的文章中也应用过《如何检测社交网络中两个人是否是敌人关系（union-find 算法）》）

public class DepthFirstPaths {private boolean marked[];
    private int[] edgeTo;
    private int s;

    DepthFirstPaths(Graph graph, int s) {
        this.s = s;
        this.marked = new boolean[graph.V()];
        this.edgeTo = new int[graph.V()];
        this.dfs(graph, s);
    }

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

    public boolean hasPathTo(int v) {return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {if (!hasPathTo(v)) {throw new IllegalStateException("s 不能到达 v");
        }
        Stack<Integer> stack = new LinkedListStack<>();
        stack.push(v);
        while (edgeTo[v] != s) {stack.push(edgeTo[v]);
            v = edgeTo[v];
        }
        stack.push(s);
        return stack;
    }
}

画图来具体跟踪深度优先搜寻的运行轨迹，记录了 edgeTo 的变动以及父链树的逐步造成

最终父链树造成了，接下来咱们来写单元测试校验下生成的父链树和理论的运行后果是否统一

@Test
public void test() {Graph graph = new Graph(8);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(0, 5);
    graph.addEdge(1, 3);
    graph.addEdge(2, 4);
    graph.addEdge(4, 3);
    graph.addEdge(5, 3);
    graph.addEdge(6, 7);

    DepthFirstPaths paths = new DepthFirstPaths(graph, 0);
    System.out.println(paths.hasPathTo(5));
    System.out.println(paths.hasPathTo(2));
    System.out.println(paths.hasPathTo(6));

    paths.pathTo(5).forEach(System.out::print);
    System.out.println();
    paths.pathTo(4).forEach(System.out::print);
    System.out.println();
    paths.pathTo(2).forEach(System.out::print);


}

验证后果齐全匹配了父链树

文中所有源码已放入到了 github 仓库:
https://github.com/silently9527/JavaCore

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源🙏

吐血整顿程序员必读书单：https://github.com/silently9527/ProgrammerBooks

微信公众号：贝塔学 Java

退出移动版