Обход в ширину и кратчайший путь

Обход в ширину начинается с вершины v, сначала посещает этот узел и помечает его как посещённый, затем последовательно посещает всех непосещённых соседей {vi,..,vj} узла v и помечает их как посещённые, затем для каждого узла из {vi,...,vj} повторяет метод посещения узла v, пока все узлы не будут посещены.

Мы можем разделить это на три шага:

  • (1) Используйте вспомогательную очередь q. Сначала поместите вершину v в очередь и пометьте её как посещённую, затем в цикле проверяйте, пуста ли очередь.
  • (2) Если очередь не пуста, извлеките первый элемент очереди, поместите в очередь все непосещённые узлы, связанные с этим элементом, и пометьте эти узлы как посещённые.
  • (3) Если очередь пуста, это означает, что все узлы были обойдены в порядке обхода в ширину.

Как показано на рисунке ниже, синий цвет справа указывает порядок обхода узлов начиная с 0, а часть ниже записывает расстояние от 0. Видно, что обход в ширину может найти кратчайший путь в невзвешенном графе.

Следующий код демонстрирует, как выполнить обход с помощью обхода в ширину и запросить кратчайший путь. Основываясь на коде из предыдущего раздела, мы добавляем глобальную переменную, массив ord, чтобы записывать порядок узлов в пути. ord[i] представляет порядок узла i в пути. В то же время конструктор соответствующим образом скорректирован: при обходе соседних узлов каждый раз, когда посещается непосещённый узел, расстояние записывается как ord[i] = ord[v] + 1. Временная сложность обхода в ширину с использованием списка смежности — O(V+E), а временная сложность с использованием матрицы смежности — O(V^2).

...
// Конструктор, алгоритм поиска пути, находит пути из точки s к другим точкам графа
public ShortestPath(Graph graph, int s){
    // Инициализация алгоритма
    G = graph;
    assert s >= 0 && s < G.V();

    visited = new boolean[G.V()];
    from = new int[G.V()];
    ord = new int[G.V()];
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        from[i] = -1;
        ord[i] = -1;
    }
    this.s = s;
    // Алгоритм поиска кратчайшего пути в неориентированном графе: начиная с s, выполнить обход в ширину всего графа
    LinkedList<Integer> q = new LinkedList<Integer>();
    q.push( s );
    visited[s] = true;
    ord[s] = 0;
    while( !q.isEmpty() ){
        int v = q.pop();
        for( int i : G.adj(v) )
            if( !visited[i] ){
                q.push(i);
                visited[i] = true;
                from[i] = v;
                ord[i] = ord[v] + 1;
            }
    }
}
...

Проверить длину кратчайшего пути из точки s в точку w; если w недостижима из s, вернуть -1.

...
public int length(int w){
    assert w >= 0 && w < G.V();
    return ord[w];
}
...

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

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

src/example/graph/ShortestPath.java код файла:

package example.graph;

import example.graph.read.Graph;

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

/**
* Обход в ширину и кратчайший путь
 */
public class ShortestPath {
    // Ссылка на граф
    private Graph G;
    // Начальная точка
    private int s;
    // Записывает, посещена ли вершина во время DFS
    private boolean[] visited;
    // Запись пути; from[i] представляет предыдущую вершину i на пути поиска
    private int[] from;
    // Записать порядок узлов в пути. ord[i] представляет порядок узла i в пути.
    private int[] ord;
    // Конструктор, алгоритм поиска пути, находит пути из точки s к другим точкам графа
    public ShortestPath(Graph graph, int s){

        // Инициализация алгоритма
        G = graph;
        assert s >= 0 && s < G.V();

        visited = new boolean[G.V()];
        from = new int[G.V()];
        ord = new int[G.V()];
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            from[i] = -1;
            ord[i] = -1;
        }
        this.s = s;
        // Алгоритм поиска кратчайшего пути в неориентированном графе: начиная с s, выполнить обход в ширину всего графа
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.push( s );
        visited[s] = true;
        ord[s] = 0;
        while( !q.isEmpty() ){
            int v = q.pop();
            for( int i : G.adj(v) )
                if( !visited[i] ){
                    q.push(i);
                    visited[i] = true;
                    from[i] = v;
                    ord[i] = ord[v] + 1;
                }
        }
    }

    // Проверить, существует ли путь из вершины s в вершину w
    public boolean hasPath(int w){
        assert w >= 0 && w < G.V();
        return visited[w];
    }
    // Получить путь из вершины s в вершину w и сохранить его в vec
    public 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
    public 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(" -> ");
        }
    }
    // Проверить длину кратчайшего пути из точки s в точку w
    // Если путь из s в w недостижим, вернуть -1
    public int length(int w){
        assert w >= 0 && w < G.V();
        return ord[w];
    }
}
Другие расширения