Алгоритм поиска пути

Алгоритм поиска пути в графе также может быть реализован с помощью поиска в глубину (DFS), находя пути из начальной точки s к другим точкам графа. В классе реализации из предыдущего подраздела добавьте глобальный массив `from` для записи путей; `from[i]` представляет предыдущий узел `i` на найденном пути.

Сначала конструктор инициализирует начальные условия алгоритма поиска пути,from = new int[G.V()]иfrom = new int[G.V()]и задаёт значения по умолчанию в цикле: все значения в массиве `visited` — `false`, а все значения в массиве `from` — `-1`. Затем для начального узла выполняется рекурсивная обработка DFS.

...
// Конструктор, алгоритм поиска пути, находит пути из точки s к другим точкам графа
public Path(Graph graph, int s){
    // Инициализация алгоритма
    G = graph;
    assert s >= 0 && s < G.V();
    visited = new boolean[G.V()];
    from = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
    }
    this.s = s;
    // Алгоритм поиска пути
    dfs(s);
}
...

Чтобы определить, существует ли путь из точки s в точку w, просто проверьте соответствующее значение в массиве `visited`.

...
boolean hasPath(int w){
    assert w >= 0 && w < G.V();
    return visited[w];
}
...

Чтобы получить конкретный путь от s к w, мы реализуем его с помощью метода `path`. Сначала определите, связаны ли они, вызвав метод `hasPath`. Как видно из конструктора, все пути можно найти, просто проследив вверх по массиву `from`.

...
Vector<Integer> path(int w){
    assert hasPath(w) ;
    Stack<Integer> s = new Stack<Integer>();
    // Пройдя по массиву from, восстановите путь от s к w и сохраните его в стеке
    int p = w;
    while( p != -1 ){
        s.push(p);
        p = from[p];
    }
    // Извлекайте элементы из стека по одному, чтобы получить упорядоченный путь от s к w
    Vector<Integer> res = new Vector<Integer>();
    while( !s.empty() )
        res.add( s.pop() );
    return res;
}
...

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код в src/example/graph/Path.java:

package example.graph;

import example.graph.read.Graph;

import java.util.Stack;
import java.util.Vector;

/**
* Поиск пути
 */
public class Path {
    // Ссылка на граф
    private Graph G;
    // Начальная точка
    private int s;
    // Записывает, посещена ли вершина во время DFS
    private boolean[] visited;
    // Запись пути; from[i] представляет предыдущую вершину i на пути поиска
    private int[] from;

    // Обход графа в глубину
    private void dfs( int v ){
        visited[v] = true;
        for( int i : G.adj(v) )
            if( !visited[i] ){
                from[i] = v;
                dfs(i);
            }
    }

    // Конструктор, алгоритм поиска пути, находит пути из точки s к другим точкам графа
    public Path(Graph graph, int s){
        // Инициализация алгоритма
        G = graph;
        assert s >= 0 && s < G.V();
        visited = new boolean[G.V()];
        from = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
        }
        this.s = s;
        // Алгоритм поиска пути
        dfs(s);
    }

    // Проверить, существует ли путь из вершины s в вершину w
    boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }

    // Получить путь из вершины s в вершину w и сохранить его в vec
    Vector<Integer> path(int w){

        assert hasPath(w) ;

        Stack<Integer> s = new Stack<Integer>();
        // Пройдя по массиву from, восстановите путь от s к w и сохраните его в стеке
        int p = w;
        while( p != -1 ){
            s.push(p);
            p = from[p];
        }

        // Извлекайте элементы из стека по одному, чтобы получить упорядоченный путь от s к w
        Vector<Integer> res = new Vector<Integer>();
        while( !s.empty() )
            res.add( s.pop() );

        return res;
    }

    // Вывести путь из вершины s в вершину w
    void showPath(int w){

        assert hasPath(w) ;

        Vector<Integer> vec = path(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}
Другие расширения