Algorithms/src/main/java/algorithms/graph/DepthFirstPath.java - develop - javapractice/JavaPractice

Algorithms/src/main/java/algorithms/graph/DepthFirstPath.java

68 строк2 KB

Zexa91x0

Algorithms - Graph

07 май 2021, 23:14

07 май 2021, 23:145d81911

package algorithms.graph;

import java.util.LinkedList;

public class DepthFirstPath {
    private boolean[] marked;
    private int[] edgeTo;
    private int source;

    /**
     * Конструктор
     * @param graph граф в котором искать путь
     * @param source начало пути.
     */
    public DepthFirstPath(Graph graph, int source) {
        this.source = source;
        edgeTo = new int[graph.getVertexCount()];
        marked = new boolean[graph.getVertexCount()];
        dfs(graph, source);
    }

    /**
     * Обход графа в глубину.
     * @param graph граф в котором искать путь
     */
    private void dfs(Graph graph, int v) {
        marked[v] = true;
        for (int temp : graph.getEdgesForVertex(v)) {
            if (!marked[temp]) {
                edgeTo[temp] = v;
                dfs(graph, temp);
            }
        }
    }

    /**
     * Узнать есть ли путь до вершины v
     *
     * @param v - вершина
     * @return - true - путь есть
     */
    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * получить список путей для вершины
     *
     * @param v - вершина
     * @return - список путей
     */
    public LinkedList<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        LinkedList<Integer> stack = new LinkedList<>();
        int vertex = v;
        while (vertex != source) {
            stack.push(vertex);
            vertex = edgeTo[vertex];
        }
        return stack;
    }

/*    public void printAll (){
        for (int i = 0; i < getVertexCount(); i++) {
            System.out.println("Start 0, End " + i + ": " + breadthFirstPath.pathTo(i));
        }
    }*/
}