Магистратура → Настройка → Комбинаторная оптимизация ↓
Алгоритмы графов
Графы - это математические структуры, используемые для моделирования парных отношений между объектами. Граф в этом контексте состоит из вершин (также называемых узлами или точками), которые соединены ребрами (также называемыми связями или линиями). Алгоритмы графов - это математические процедуры, разработанные для решения задач, связанных с графами.
Важность алгоритмов графов
Графы имеют фундаментальное значение во многих областях, включая информатику, биологию и социальные науки. Они помогают решать такие задачи, как потоки в сети, нахождение кратчайших путей, создание остовных деревьев и многое другое. Давайте рассмотрим некоторые основные и продвинутые алгоритмы графов.
Основные определения
Перед тем как перейти к алгоритмам, важно понять некоторые базовые термины, связанные с графами.
- Вершина (или узел): Точка в графе, где сходятся ребра.
- Ребро (или связь): Связь между двумя вершинами.
- Смежность: Две вершины смежны, если они напрямую соединены ребром.
- Путь: Последовательность ребер, соединяющих последовательность вершин.
- Цикл: Путь, который начинается и заканчивается в одной и той же вершине.
- Связный граф: Граф, в котором существует путь между каждой парой вершин.
Типы графов
- Ориентированный граф (диграф): Граф, в котором ребра имеют направления. Каждое ребро представляет собой упорядоченную пару вершин.
- Неориентированный граф: Граф, в котором ребра не имеют направления. Каждое ребро представляет собой неупорядоченную пару вершин.
- Взвешенный граф: Граф, в котором каждому ребру присвоено числовое значение (вес).
- Невзвешенный граф: Граф, в котором ребрами не присвоены веса.
- Полный граф: Граф, в котором существует ровно одно ребро между каждой парой вершин.
Представление графов
Графы могут быть представлены двумя основными способами:
Матрица смежности
Матрица смежности - это двумерный массив, в котором каждый элемент указывает, существует ли ребро между парами вершин.
a = [
[0, 1, 0, 0],
[1, 0, 1, 1],
[0, 1, 0, 1],
[0, 1, 1, 0]
]
Эта матрица показывает граф с 4 вершинами и ребрами между парами (0,1), (1,2), (1,3) и (2,3).
Список смежности
Список смежности представляет граф в виде списка вершин, где каждая вершина имеет свой собственный список смежных вершин.
{
0: [1],
1: [0, 2, 3],
2: [1, 3],
3: [1, 2]
}
В этом списке вершина 0 соединена с вершиной 1, вершина 1 соединена с вершинами 0, 2, 3 и так далее.
Алгоритмы обхода графов
Обход графа означает процесс посещения каждой вершины графа. Существует два основных способа обхода графа:
Поиск в ширину (BFS)
BFS - это метод, который проходит по графу, исследуя соседние узлы, находящиеся на текущей глубине, перед переходом к узлам, находящимся на следующем уровне глубины.
def bfs(graph, start):
visited = set()
queue = [start]
while queue:
vertex = queue.pop(0)
if vertex not in visited:
visited.add(vertex)
queue.extend(set(graph[vertex]) - visited)
return visited
В приведенном выше коде граф обходится, начиная с вершины start. Метод BFS использует очередь для отслеживания вершин, которые нужно посетить далее.
Пример работы BFS
Приведенное выше SVG показывает простой граф с вершинами, пронумерованными от 0 до 3. Начиная с вершины 0, BFS будет посещать узлы в следующем порядке: 0, 1, 3, 2.
Поиск в глубину (DFS)
DFS - это метод обхода, в котором приоритет отдается глубине, и перемещение идет как можно дальше по ветви, прежде чем происходит возврат.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for next in graph[start]:
if next not in visited:
dfs(graph, next, visited)
return visited
В коде DFS метод вызывается рекурсивно, и стек используется через вызовы функций для отслеживания пути.
Пример работы DFS
Для того же графа DFS будет посещать узлы в следующем порядке: 0, 1, 2, 3.
Алгоритм поиска кратчайшего пути
Цель алгоритмов графов – часто найти кратчайший путь между узлами. Вот два известных алгоритма поиска кратчайшего пути:
Алгоритм Дейкстры
Алгоритм Дейкстры находит кратчайший путь от начальной вершины до всех остальных вершин в взвешенном графе.
import heapq
def dijkstra(graph, start):
queue = []
heapq.heappush(queue, (0, start))
distances = {node: float('infinity') for node in graph}
distances[start] = 0
while queue:
current_distance, current_node = heapq.heappop(queue)
if current_distance > distances[current_node]:
continue
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(queue, (distance, neighbor))
return distances
Этот алгоритм использует очередь для быстрого получения ребра с минимальным расстоянием, применяя приоритетную очередь (минимальную кучу).
Алгоритм Беллмана-Форда
Алгоритм Беллмана-Форда вычисляет кратчайшие пути от одной исходной вершины до всех остальных вершин в графе. Он может обрабатывать графы с отрицательными весами.
def bellman_ford(graph, start):
distance = {i: float('inf') for i in graph}
distance[start] = 0
for _ in range(len(graph) - 1):
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
distance[neighbor] = distance[vertex] + weight
for vertex in graph:
for neighbor, weight in graph[vertex].items():
if distance[vertex] + weight < distance[neighbor]:
raise ValueError("Граф содержит цикл с отрицательным весом")
return distance
В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда хорошо работает с графами, содержащими ребра с отрицательными весами. Он повторно проверяет каждое ребро, чтобы убедиться, что найдены оптимальные пути.
Алгоритм минимального остовного дерева (MST)
Минимальное остовное дерево связного неориентированного графа — это подмножество ребер, которое соединяет все вершины без циклов и с минимальной возможной общей суммой весов ребер.
Алгоритм Краскала
Алгоритм Краскала строит MST, добавляя ребра одно за другим, начиная с самого короткого, и добавляя только те ребра, которые не образуют циклы.
def kruskal(graph):
parent = {}
def find(n):
while parent[n] != n:
n = parent[n]
return n
def union(n1, n2):
root1 = find(n1)
root2 = find(n2)
parent[root2] = root1
graph.sort(key=lambda x: x[2])
for n1, n2, _ in graph:
parent[n1] = n1
parent[n2] = n2
mst = []
for n1, n2, weight in graph:
if find(n1) != find(n2):
union(n1, n2)
mst.append((n1, n2, weight))
return mst
Этот алгоритм начинает с сортировки всех ребер по весу. Он использует структуру данных union-find для отслеживания соединенных компонентов и гарантирует, что циклы не будут образовываться.
Алгоритм Прима
Алгоритм Прима строит MST, начиная с произвольной вершины и последовательно добавляя ребро с наименьшим весом от уже выбранных вершин к еще не выбранным вершинам.
import heapq
def prim(graph, start):
mst = []
visited = set()
min_edges = [(0, start, None)]
while min_edges:
weight, vertex, frm = heapq.heappop(min_edges)
if vertex in visited:
continue
visited.add(vertex)
if frm is not None:
mst.append((frm, vertex, weight))
for next_vertex, next_weight in graph[vertex].items():
if next_vertex not in visited:
heapq.heappush(min_edges, (next_weight, next_vertex, vertex))
return mst
Алгоритм Прима использует приоритетную очередь, чтобы всегда расширять узел в текущей границе с наименьшей стоимостью.
Заключение
Алгоритмы графов предоставляют решения множества задач, связанных с сетями узлов и ребер. Будь то нахождение кратчайшего пути, оптимальных соединений или обход узлов, эти алгоритмы играют важную роль в эффективном решении сложных задач. Понимание основных определений, представлений и основных алгоритмов, таких как BFS, DFS, Дейкстра, Беллман-Форд, Краскал и Прим, имеет решающее значение для использования алгоритмов графов в реальных приложениях.
комментарии