Рассмотрим алгоритм поиска в глубину в графе (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
