Поиск в глубину (DFS) — это алгоритм обхода или поиска древовидных или графовых структур данных. Начинают с корня (выбирая произвольный узел в качестве корня Graph) и исследуют как можно дальше каждую ветвь, прежде чем Backtracking.
На следующем Graphе показан порядок, в котором узлы обнаруживаются в DFS.
Поиск в глубину по деревьям
Дерево — это неориентированный graph, в котором любые две вершины соединены ровно одним путем. Другими словами, любой ациклический связный graph является деревом. Для дерева у нас есть следующие методы обхода:
- Предварительный заказ: посетить каждый узел перед его дочерними элементами.
- Почтовый заказ: посетить каждый узел после его потомков.
- В целях (for бинарные деревья только): посетить левое поддерево, узел, правое поддерево.
Они уже подробно описаны в отдельных постах.
Поиск в глубину в Graph
А Поиск в глубину (DFS) это способ обхода graphs, тесно связанный с обходом дерева в прямом порядке. Ниже приведена рекурсивная реализация обхода предварительного порядка:
procedure preorder(treeNode v)
{
visit(v);
for each child u of v
preorder(u);
}
{
visit(v);
for each child u of v
preorder(u);
}
Чтобы превратить это в алгоритм обхода Graph, замените “дочерний” на “соседний”. Но чтобы предотвратить бесконечные циклы, следите за уже обнаруженными вершинами и не посещайте их повторно.
procedure dfs(vertex v)
{
visit(v);
for each neighbor u of v
if u is undiscovered
call dfs(u);
}
{
visit(v);
for each neighbor u of v
if u is undiscovered
call dfs(u);
}
Рекурсивный алгоритм может быть реализован на C++, Java и Python следующим образом:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include <iostream> #include <vector> using namespace std; // Структура данных для хранения ребра Graph struct Edge { int src, dest; }; // Класс для представления graphического объекта class Graph { public: // вектор векторов для представления списка смежности vector<vector<int>> adjList; // Конструктор Graphа Graph(vector<Edge> const &edges, int n) { // изменить размер вектора, чтобы он содержал `n` элементов типа `vector<int>` adjList.resize(n); // добавляем ребра в неориентированный graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Функция для обхода DFS на Graphе на Graphе void DFS(Graph const &graph, int v, vector<bool> &discovered) { // помечаем текущий узел как обнаруженный discovered[v] = true; // печатаем текущий узел cout << v << " "; // делаем для каждого ребра (v, u) for (int u: graph.adjList[v]) { // если `u` еще не обнаружен if (!discovered[u]) { DFS(graph, u, discovered); } } } int main() { // vector ребер Graph согласно схеме выше vector<Edge> edges = { // Обратите внимание, что узел 0 не подключен {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11} }; // общее количество узлов в Graph (от 0 до 12) int n = 13; // строим graph из заданных ребер Graph graph(edges, n); // чтобы отслеживать, открыта вершина или нет vector<bool> discovered(n); // Выполняем обход DFS от всех необнаруженных узлов к // покрываем все связные компоненты Graph for (int i = 0; i < n; i++) { if (discovered[i] == false) { DFS(graph, i, discovered); } } return 0; } |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; // Класс для хранения ребра Graph class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // Класс для представления graphического объекта class Graph { // Список списков для представления списка смежности List<List<Integer>> adjList = null; // Конструктор Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // добавляем ребра в неориентированный graph for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Функция для обхода DFS на Graphе на Graphе public static void DFS(Graph graph, int v, boolean[] discovered) { // помечаем текущий узел как обнаруженный discovered[v] = true; // печатаем текущий узел System.out.print(v + " "); // делаем для каждого ребра (v, u) for (int u: graph.adjList.get(v)) { // если `u` еще не обнаружен if (!discovered[u]) { DFS(graph, u, discovered); } } } public static void main(String[] args) { // Список ребер Graph согласно приведенной выше диаграмме List<Edge> edges = Arrays.asList( // Обратите внимание, что узел 0 не подключен new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3), new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9), new Edge(8, 12), new Edge(9, 10), new Edge(9, 11) ); // общее количество узлов в Graph (от 0 до 12) int n = 13; // строим graph из заданных ребер Graph graph = new Graph(edges, n); // чтобы отслеживать, открыта вершина или нет boolean[] discovered = new boolean[n]; // Выполняем обход DFS от всех необнаруженных узлов к // покрываем все связные компоненты Graph for (int i = 0; i < n; i++) { if (!discovered[i]) { DFS(graph, i, discovered); } } } } |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
# Класс для представления graphического объекта class Graph: # 1ТП4Т Конструктор def __init__(self, edges, n): # Список списков для представления списка смежности self.adjList = [[] for _ in range(n)] # добавляет ребра в неориентированный graph for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Функция для обхода DFS на Graphе на Graphе def DFS(graph, v, discovered): discovered[v] = True # пометить текущий узел как обнаруженный print(v, end=' ') # распечатать текущий узел # делаем для каждого ребра (v, u) for u in graph.adjList[v]: if not discovered[u]: #, если `u` еще не обнаружен DFS(graph, u, discovered) if __name__ == '__main__': # Список ребер Graph согласно приведенной выше схеме edges = [ # Обратите внимание, что узел 0 не подключен (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4), (3, 5), (8, 9), (8, 12), (9, 10), (9, 11) ] # общее количество узлов в Graph (от 0 до 12) n = 13 # строит graph по заданным ребрам graph = Graph(edges, n) # для отслеживания обнаружена вершина или нет discovered = [False] * n # Выполнить обход DFS от всех необнаруженных узлов к # охватывает все связанные компоненты Graph for i in range(n): if not discovered[i]: DFS(graph, i, discovered) |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Временная сложность обхода DFS составляет O(V + E), куда V а также E - общее количество вершин и ребер в Graph соответственно. Обратите внимание, что O(E) может варьироваться между O(1) а также O(V2), в зависимости от того, насколько плотен graph.
Итеративная реализация DFS
Нерекурсивная реализация DFS похожа на нерекурсивная реализация BFS но отличается от него двумя способами:
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 |
#include <iostream> #include <stack> #include <vector> using namespace std; // Структура данных для хранения ребра Graph struct Edge { int src, dest; }; // Класс для представления graphического объекта class Graph { public: // вектор векторов для представления списка смежности vector<vector<int>> adjList; // Конструктор Graphа Graph(vector<Edge> const &edges, int n) { // изменить размер вектора, чтобы он содержал `n` элементов типа `vector<int>` adjList.resize(n); // добавляем ребра в неориентированный graph for (auto &edge: edges) { adjList[edge.src].push_back(edge.dest); adjList[edge.dest].push_back(edge.src); } } }; // Выполнить итеративный поиск в глубину на Graph, начиная с вершины `v` void iterativeDFS(Graph const &graph, int v, vector<bool> &discovered) { // создаем stack, используемый для итеративной DFS stack<int> stack; // помещаем исходный узел в stack stack.push(v); // цикл до тех пор, пока stack не станет пустым while (!stack.empty()) { // Извлечь вершину из stack v = stack.top(); stack.pop(); // если вершина уже обнаружена, // игнорируй это if (discovered[v]) { continue; } // мы доберемся сюда, если выскочившая вершина `v` еще не обнаружена; // напечатать `v` и обработать его необнаруженные соседние узлы в stack discovered[v] = true; cout << v << " "; // делаем для каждого ребра (v, u) // мы используем обратный итератор (почему?) for (auto it = graph.adjList[v].rbegin(); it != graph.adjList[v].rend(); it++) { int u = *it; if (!discovered[u]) { stack.push(u); } } } } int main() { // vector ребер Graph согласно схеме выше vector<Edge> edges = { // Обратите внимание, что узел 0 не подключен {1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4}, {3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11} // {6, 9} вводит цикл }; // общее количество узлов в Graph (от 0 до 12) int n = 13; // строим graph из заданных ребер Graph graph(edges, n); // чтобы отслеживать, открыта вершина или нет vector<bool> discovered(n); // Выполняем итеративный обход в глубину от всех необнаруженных узлов к // покрываем все связные компоненты Graph for (int i = 0; i < n; i++) { if (discovered[i] == false) { iterativeDFS(graph, i, discovered); } } return 0; } |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Stack; // Класс для хранения ребра Graph class Edge { int source, dest; public Edge(int source, int dest) { this.source = source; this.dest = dest; } } // Класс для представления graphического объекта class Graph { // Список списков для представления списка смежности List<List<Integer>> adjList = null; // Конструктор Graph(List<Edge> edges, int n) { adjList = new ArrayList<>(); for (int i = 0; i < n; i++) { adjList.add(new ArrayList<>()); } // добавляем ребра в неориентированный graph for (Edge edge: edges) { int src = edge.source; int dest = edge.dest; adjList.get(src).add(dest); adjList.get(dest).add(src); } } } class Main { // Выполнить итеративный поиск в глубину на Graph, начиная с вершины `v` public static void iterativeDFS(Graph graph, int v, boolean[] discovered) { // создаем stack, используемый для итеративной DFS Stack<Integer> stack = new Stack<>(); // помещаем исходный узел в stack stack.push(v); // цикл до тех пор, пока stack не станет пустым while (!stack.empty()) { // Извлечь вершину из stack v = stack.pop(); // если вершина уже обнаружена, игнорируем ее if (discovered[v]) { continue; } // мы доберемся сюда, если выскочившая вершина `v` еще не обнаружена; // напечатать `v` и обработать его необнаруженные соседние узлы в stack discovered[v] = true; System.out.print(v + " "); // делаем для каждого ребра (v, u) List<Integer> adjList = graph.adjList.get(v); for (int i = adjList.size() - 1; i >= 0; i--) { int u = adjList.get(i); if (!discovered[u]) { stack.push(u); } } } } public static void main(String[] args) { // Список ребер Graph согласно приведенной выше диаграмме List<Edge> edges = Arrays.asList( // Обратите внимание, что узел 0 не подключен new Edge(1, 2), new Edge(1, 7), new Edge(1, 8), new Edge(2, 3), new Edge(2, 6), new Edge(3, 4), new Edge(3, 5), new Edge(8, 9), new Edge(8, 12), new Edge(9, 10), new Edge(9, 11) // (6, 9) вводит цикл ); // общее количество узлов в Graph (от 0 до 12) int n = 13; // строим graph из заданных ребер Graph graph = new Graph(edges, n); // чтобы отслеживать, открыта вершина или нет boolean[] discovered = new boolean[n]; // Выполняем итеративный обход в глубину от всех необнаруженных узлов к // покрываем все связные компоненты Graph for (int i = 0; i < n; i++) { if (!discovered[i]) { iterativeDFS(graph, i, discovered); } } } } |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
from collections import deque # Класс для представления graphического объекта class Graph: # 1ТП4Т Конструктор def __init__(self, edges, n): # Список списков для представления списка смежности self.adjList = [[] for _ in range(n)] # добавляет ребра в неориентированный graph for (src, dest) in edges: self.adjList[src].append(dest) self.adjList[dest].append(src) # Выполнить итеративную поиск в глубину на Graph, начиная с вершины `v` def iterativeDFS(graph, v, discovered): # создает stack, используемый для выполнения итеративной DFS. stack = deque() # помещает исходный узел в stack stack.append(v) # Цикл # до тех пор, пока stack не станет пустым while stack: # Извлечение вершины из stack v = stack.pop() #, если вершина уже обнаружена, игнорировать ее if discovered[v]: continue # мы достигнем здесь, если выскочившая вершина `v` еще не обнаружена; # печатает `v` и обрабатывает его необнаруженные соседние узлы в stack discovered[v] = True print(v, end=' ') # делаем для каждого ребра (v, u) adjList = graph.adjList[v] for i in reversed(range(len(adjList))): u = adjList[i] if not discovered[u]: stack.append(u) if __name__ == '__main__': # Список ребер Graph согласно приведенной выше схеме edges = [ # Обратите внимание, что узел 0 не подключен (1, 2), (1, 7), (1, 8), (2, 3), (2, 6), (3, 4), (3, 5), (8, 9), (8, 12), (9, 10), (9, 11) # (6, 9) вводит цикл ] # общее количество узлов в Graph (от 0 до 12) n = 13 # строит graph по заданным ребрам graph = Graph(edges, n) # для отслеживания обнаружена вершина или нет discovered = [False] * n # Выполнить итеративный обход DFS от всех необнаруженных узлов к # охватывает все связанные компоненты Graph for i in range(n): if not discovered[i]: iterativeDFS(graph, i, discovered) |
результат:
0 1 2 3 4 5 6 7 8 9 10 11 12
Приложения ДФС
- Нахождение компонент связности в Graph.
- Топологическая сортировка в DAG (направленный ациклический graph).
- Нахождение компонентов 2/3 (реберной или вершинной) связности.
- Finding the мосты Graph.
- Нахождение сильно связные компоненты.
- Решение головоломок только с одним решениемнапример, лабиринты.
- Нахождение двусвязности в graphs и многое другое…
Также см:
Поиск в глубину (DFS) – вопросы интервью и практические задачи
Использованная литература: https://www.ics.uci.edu/~eppstein/161/960215.html