Граф — это совокупность вершин и связей между ними (ребер).
Есть два основных метода обхода графа: Поиск в глубину (dfs/Depth-first search)и Поиск в ширину(bfs/breadth-first search).
Стратегия поиска в глубину заключается в том, чтобы вначале пойти вглубь графа, насколько это возможно. В то время как при поиске в ширину, граф обходится, как бы “по слоям”. Сначала все соседи от начальной вершины, потом соседи соседей и т.д.
Есть две реализации алгоритма поиска в глубину: рекурсивная и через стек.
Временная сложность алгоритма: O(E + V).
Space complexity: O(V).
V — число вершин в графе, E — число ребер.
Реализация через рекурсию:
void dfs(Node root, Set<Node> visited) {
if (root == null) {
return;
}
visit(root);
visited.add(root);
for (Node neighbour : root.getNeighbours()) {
if (!visited.contains(neighbour)) {
dfs(neighbour, visited);
}
}
}
Node — это class вершины графа. Нам необходимо хранить список уже посещенных вершин, чтобы не ходить по одним и тем же вершинам кругами.
visit(Node node) это некий метод или код, который мы хотим выполнить при посещении вершины. Конкретный код будет зависеть от задачи.
Работает алгоритм так: посещаем первую вершину, помечаем ее как посещенную, смотрим на список ее соседей и если мы их еще не посещали, то рекурсивно вызываем функцию уже для соседей.
Реализация при помощи стека:
void dfs(Node root) {
if (root == null) {
return;
}
Set<Node> visited = new HashSet<>();
Stack<Node> stack = new Stack<>();
stack.push(root);
visited.add(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
visit(node);
for (Node neighbour : node.getNeighbours()) {
if (!visited.contains(neighbour)) {
visited.add(neighbour);
stack.push(neighbour);
}
}
}
}
Со стеком. Помещаем первую вершину в стек, помечаем ее как посещенную. Пока стек не пуст: получаем вершину графа из стека, посещаем ее, смотрим на ее соседей, те вершины, которые мы еще не посетили, помечаем их как посещенными и помещаем в стек.
class Node можно реализовать так:
class Node {
private int value;
private final List<Node> neighbours;
public Node(int value, List<Node> neighbours) {
this.value = value;
this.neighbours = neighbours;
}
public List<Node> getNeighbours() {
return this.neighbours;
}
public int getValue() {
return this.value;
}
}
Или, для простоты, на собеседовании можно себе представлять так:
class Node {
int value;
List<Node> neighbours;
public Node(int value, List<Node> neighbours) {
this.value = value;
this.neighbours = neighbours;
}
}
Это позволит обращаться к полям класса:
Node node = ...
node.value //Получить значение
node.neighbours // Получить всех соседей
Давайте посмотрим по шагам как будет работать рекурсивный поиск в глубину на таком графе:
Я буду помечать зеленым цветом уже посещенные вершины (visited):
Шаг 1:
Шаг 2:
Шаг 3:
Шаг 4:
Шаг 5:
Шаг 6:
Шаг 7:
Для реализации через стек, обход будет несколько другой. Он вначале пойдет вправо. Но также, обход будет сначала на максимальную глубину. 1->3->6->2->5->4->7
Посмотрим более подробно на состояние стека и последовательность посещения для реализации DFS через стек. Посещенные вершины также буду помечать зеленым.
Помечаем первую вершину, добавляем ее в стек. В цикле на первой итерации достаем ее из стека и посещаем (visit(node)).
Соседние вершины к 1 это вершины 2 и 3. Они еще не помечены, помещаем их в стек и помечаем.
На следующей итерации цикла while достаем из вершины стека 3 и посещаем ее. Смежные/соседние вершины к 3 это 1 и 6. 1 уже помечена. Поэтому в стек добавляем 6 и помечаем ее.
Достаем из стека 6 и посещаем ее. У 6 только одна смежная вершина — 3. Но она уже помечена. Поэтому переходим на следующую итерацию цикла while.
Достаем из стека 2. Посещаем ее. Смотрим на ее смежные вершины: 1, 4, 5. 1 уже помечена. Поэтому помечаем 4 и 5 и помещаем их в стек.
Достаем из стека 5. Посещаем ее. У 5 одна смежная вершина 2. Но она уже помечена, поэтому ничего не добавляем в стек.
Достаем 4 из стека, посещаем ее. У нее смежные это 2 и 7. 2 уже помечена. Поэтому помечаем 7 и помещаем ее в стек.
Достаем 7 из стека. Посещаем ее. У 7 одна смежная вершина — 4. Она уже помечена. На следующей итерации цикла while стек будет пуст — алгоритм закончен.
Top comments (0)