Обход в глубину и компоненты связности

Основная идея поиска в глубину заключается в том, чтобы сначала взять непосещённую вершину в качестве начальной и, двигаясь по рёбрам текущей вершины, переходить к непосещённой вершине. Когда непосещённых вершин нет, вернуться к предыдущей вершине и продолжать пробовать другие вершины, пока все вершины не будут посещены.

Граф в приведённом ниже примере начинает обход с 0, а порядок показан на рисунке справа:

Максимальный связный подграф неориентированного графа G называется компонентой связности (или связной ветвью) графа G. Связный граф имеет только одну компоненту связности — самого себя; несвязный неориентированный граф имеет несколько компонент связности. Между компонентами связности нет рёбер. Поиск в глубину можно использовать для нахождения компонент связности.

Далее на примере поиска компонент связности реализуется обход графа в глубину, называемый dfs. В приведённом ниже фрагменте кода массив visited хранит, был ли узел посещён во время dfs, ccount хранит количество компонент связности, массив id представляет метку компоненты связности, соответствующую каждому узлу, а два узла с одинаковым значением id означают, что они принадлежат одной и той же компоненте связности.

...
// Конструктор, находит компоненты связности невзвешенного графа
public Components(Graph graph){
    // Инициализация алгоритма
    G = graph;
    visited = new boolean[G.V()];
    id = new int[G.V()];
    ccount = 0;
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        id[i] = -1;
    }
    // Найти компоненты связности графа
    for( int i = 0 ; i < G.V() ; i ++ )
        if( !visited[i] ){
            dfs(i);
            ccount ++;
        }
}
...

Обход графа в глубину — это рекурсивный процесс; код реализации:

...
// Обход графа в глубину
void dfs( int v ){

    visited[v] = true;
    id[v] = ccount;

    for( int i: G.adj(v) ){
        if( !visited[i] )
            dfs(i);
    }
}
...

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

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

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

package example.graph;

import example.graph.read.Graph;

/**
* Обход в глубину
 */

public class Components {

    Graph G;                    // Ссылка на граф
    private boolean[] visited;  // Отмечает, посещён ли узел во время обхода в глубину
    private int ccount;         // Записывает количество компонент связности
    private int[] id;           // Метка компоненты связности, соответствующая каждому узлу

    // Обход графа в глубину
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;

        for( int i: G.adj(v) ){
            if( !visited[i] )
                dfs(i);
        }
    }

    // Конструктор, находит компоненты связности невзвешенного графа
    public Components(Graph graph){

        // Инициализация алгоритма
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // Найти компоненты связности графа
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // Возвращает количество компонент связности графа
    int count(){
        return ccount;
    }

    // Проверяет, связаны ли узлы v и w
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }
}
Другие расширения