Графы. Поиск в глубину (depth-first search, DFS)

Рассмотрим алгоритм поиска в глубину в графе (depth-first search). Поиск в глубину - один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой не пройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в следующих задачах:

• алгоритмы поиска одно- и двусвязных компонент


• топологическая сортировка


• поиск путей в графе


• поиск лексикографически первого пути в графе


• проверка графа на ацикличность и нахождение цикла


• поиск мостов (мостом называется такое ребро, удаление которого делает граф несвязным)

Рассмотрим следующий граф:


Для него нужно выполнить следующее:
1) сделать поиск в глубину. На каждом шаге из нескольких доступных вершин выбирать лексикографически первую вершину.
2) проставить для каждой вершины время входа и время выхода из нее
3) распечатать вершины в порядке входа (т.е. отсортировать по возрастанию времени входа), указав для каждой вершины время входа и выхода

Сначал создадим этот граф:

graph = new UndirectedGraph();
graph.addEdge("A", "B");
graph.addEdge("A", "E");
graph.addEdge("B", "C");
graph.addEdge("B", "E");
graph.addEdge("C", "F");
graph.addEdge("E", "F");
graph.addEdge("F", "I");
 
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("G", "H");

Затем, поскольку нужно выбирать лексикографически первую вершину, возьмем список вершин и отсортируем их по имени по возрастанию. В результате, список vertexList будет содержать имена всех вершин графа, отсортированные лексикографически:

Map<String, List<String>> vm = graph.getVertexMap();
List<String> vertexList = new ArrayList<String>(vm.size());
vertexList.addAll(vm.keySet());
Collections.sort(vertexList); 
 

Теперь пришло время выполнить поиск в глубину:

for (String v : vertexList) {
    dfs(v);
}

Наконец, выполняем последний пункт задания - распечатываем вершины в порядке входа:

for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
    Mark m = entry.getValue();
    System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
}

Здесь мы используем вспомогательный класс Mark, который содержит время входа и выхода:

static class Mark {
    public Mark(int pre, int post) {
        this.pre  = pre;
        this.post = post;
    }
    public int pre;
    public int post;
};

Хеш-таблица visitedMap содержит посещенные вершины графа и соотвествующее время входа/выхода. В качестве реализации visitedMap мы выбрали java.util.LinkedHashMap. Эта реализация позволяет перебрать все добавленные в хеш-таблицу элементы в том порядке, в котором они были добавлены (а не в произвольном порядке, как обычная java.util.HashMap). Это как раз и дает нам возможность распечатать вершины графа в порядке входа.

Теперь рассмотрим сам алгоритм поиска в глубину:

static void dfs(String vertexName) {
    if (visitedMap.containsKey(vertexName)) return;
 
    // set pre (time of enter)
    visitedMap.put(vertexName, new Mark(counter,-1));
    counter++;
 
    // retrieve adjacent vertices
    Map<String, List<String>> vm = graph.getVertexMap();
    List<String> adjacentVertices = vm.get(vertexName);
 
    for (String v : adjacentVertices) {
        if (visitedMap.containsKey(v)) continue;
        dfs(v);
    }
 
    // set post (time of exit)
    Mark m = visitedMap.get(vertexName);
    m.post = counter++;
}

Мне кажется, что код и комментарии в нем говорят сами за себя :-)

Наконец, приведем полный исходный код решения задачи (Problem1.java):

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
import java.util.List;
import java.util.Map;
 
public class Problem1 {
 
    static class Mark {
        public Mark(int pre, int post) {
            this.pre  = pre;
            this.post = post;
        }
        public int pre;
        public int post;
    };
 
    // our graph
    static UndirectedGraph graph;
    // map of visited vertices
    static Map<String, Mark> visitedMap = new LinkedHashMap<String, Mark>();
    // time counter
    static int counter = 1;
 
    public static void main(String[] args) {
 
        graph = new UndirectedGraph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "E");
        graph.addEdge("B", "C");
        graph.addEdge("B", "E");
        graph.addEdge("C", "F");
        graph.addEdge("E", "F");
        graph.addEdge("F", "I");
 
        graph.addEdge("D", "G");
        graph.addEdge("D", "H");
        graph.addEdge("G", "H");
 
        Map<String, List<String>> vm = graph.getVertexMap();
 
        List<String> vertexList = new ArrayList<String>(vm.size());
        vertexList.addAll(vm.keySet());
        Collections.sort(vertexList);   
 
        for (String v : vertexList) {
            dfs(v);
        }
 
        for (Map.Entry<String, Mark> entry : visitedMap.entrySet()) {
            Mark m = entry.getValue();
            System.out.format("%1$s : (%2$d, %3$d)\n", entry.getKey(), m.pre, m.post);
        }
    }    
 
    static void dfs(String vertexName) {
        if (visitedMap.containsKey(vertexName)) return;
 
        // set pre (time of enter)
        visitedMap.put(vertexName, new Mark(counter,-1));
        counter++;
 
        // retrieve adjacent vertices
        Map<String, List<String>> vm = graph.getVertexMap();
        List<String> adjacentVertices = vm.get(vertexName);
 
        for (String v : adjacentVertices) {
            if (visitedMap.containsKey(v)) continue;
            dfs(v);
        }
 
        // set post (time of exit)
        Mark m = visitedMap.get(vertexName);
        m.post = counter++;
    }
}

При запуске получаем следующий вывод:

$>java Problem1
A : (1, 12)
B : (2, 11)
C : (3, 10)
F : (4, 9)
E : (5, 6)
I : (7, 8)
D : (13, 18)
G : (14, 17)
H : (15, 16)


Или, в графическом виде:


Дополнительные ссылки:
Поиск в глубину - Википедия
Поиск в глубину в графе - MAXimal