算法分析-路径查找

在无向图中查找任意一条到达某个顶点的路径

代码：

package com.chenqing.test.graph;

import com.chenqing.test.linearList.stack.Realization;

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

    public DeepFirstPaths(Graph graph, int s) {
        this.marked = new boolean[graph.getV()];
        this.s = s;
        this.edgeTo = new int[graph.getV()];
    }

    private void dfs(Graph graph, int s){
        this.marked[s] = true;
        for (Integer i : graph.getTable(s)) {
            if(!marked[i]){
                this.edgeTo[i] = s;
                dfs(graph, i);
            }
        }
    }

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

    public Realization<Integer> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Realization<Integer> integers = new Realization<>();
        for (int i = v; v != s; i=edgeTo[i]) {
            integers.push(i);
        }
        integers.push(s);
        return integers;
    }
}