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

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

78 строк2 KB

Zexa91x0

Algorithms - Graph

07 май 2021, 23:14

07 май 2021, 23:145d81911

package algorithms.graph;

import java.util.LinkedList;

public class BreadthFirstPath {
    private boolean[] marked;
    private int[] edgeTo;
    private int[] distTo;
    private int source;
    private final int INFIBITY = Integer.MAX_VALUE;

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

    /**
     * Обход графа в ширину.
     * @param graph граф в котором искать путь
     * @param source начало пути.
     */
    private void dfs(Graph graph, int source) {
        LinkedList<Integer> queue = new LinkedList<>();
        queue.addLast(source);
        marked[source] = true;
        distTo[source] = 0;
        while (!queue.isEmpty()) {
            int vertex = queue.removeFirst();
            for (int w : graph.getEdgesForVertex(vertex)) {
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = vertex;
                    distTo[w] = distTo[vertex] + 1;
                    queue.addLast(w);
                }
            }
        }
    }

    /**
     * Узнать есть ли путь до вершины 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;
    }

}