17-09-2023
Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.
Содержание |
Пусть задан граф , где — множество вершин графа, — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
DFS()
.Процедура DFS (параметр — вершина )
DFS(w)
.public static void search(Node node, Node goal) // Node - вершина графа { if (node.equals(goal)) { System.out.println(node)); } else { for (int i = 0; i < node.getNode().size(); i++) // Вызываем этот же метод для каждой смежной вершины { if (stack.add(node.getNode().get(i))) // Проверяем, вызывали ли мы этот метод для вершины node.getNode().get(i) { search(node.getNode().get(i), goal); } } } }
vector < vector<int> > graph; vector<bool> used; void dfs(int node_index) { used[node_index] = true; for (vector<int>::iterator i = graph[node_index].begin(); i != graph[node_index].end(); ++i) { if ( !used[*i] ) dfs(*i); } }
const MAX_N = 10; var graph: array [1..MAX_N, 1..MAX_N] of boolean; // массив для определения графа visited: array [1..MAX_N] of boolean; procedure dfs(v: integer); var i: integer; begin visited[v] := true; for i := 1 to MAX_N do if graph[v, i] and not visited[i] then dfs(i); end;
Алгоритмы поиска на графах |
---|
Поиск в глубину.