Деревья и обходы графов — Дискретная математика

Основные определения

Дерево – это связный ациклический граф.

Алгоритм поиска в глубину позволяет последовательно посещать все вершины графа, начиная с заданной начальной вершины.

```python def dfs(graph, start): visited = set() stack = [start]

while stack: vertex = stack.pop() if vertex not in visited: visited.add(vertex) for neighbor in graph[vertex]: stack.append(neighbor) ```

Поиск в ширину посещает сначала ближайшие вершины от стартовой, затем более дальние.

```python def bfs(graph, start): visited = set() queue = [start]

while queue: vertex = queue.pop(0) if vertex not in visited: visited.add(vertex) for neighbor in graph[vertex]: queue.append(neighbor) ```

Остовное дерево – минимальное дерево, содержащее все вершины исходного графа.

Алгоритм Краскала: сортирует рёбра по возрастанию веса и добавляет их в дерево до тех пор, пока не будут охвачены все вершины.

$E = \{(u,v) | u < v\}, \quad w(u,v)$

Алгоритм Прима: строит дерево из одной начальной вершины, добавляя рёбра с минимальной стоимостью.

Выбираем начальную вершину.
Находим ребро минимального веса, ведущее из уже охваченных вершин к необработанным.
Добавляем найденное ребро в дерево.
Повторяем шаги до полного охвата всех вершин.