Структура теории графов
В информатике графы широко используются для моделирования социальных сетей (пользователи — узлы, дружеские связи — рёбра), веб-ссылок (веб-страницы — узлы, гиперссылки — рёбра), коммуникационных сетей и даже задач планирования маршрутов.
ГрафЭто как граф отношений социальной сети:
- Узел (вершина): каждый человек в социальной сети
- Ребро: отношения между людьми (друзья, подписки и т. д.)
- Вес: сила отношений (близость, частота взаимодействия и т. д.)
Представьте транспортную сеть в вашем городе: различные места (такие как дом, школа, торговый центр) являютсяточками, дороги, соединяющие эти места, являютсялиниями. Граф (Graph) — это математическая абстракция связей между точками и линиями; он используется для представленияСложные связи между сущностямиструктура данных.
Примеры из реальной жизни:
- Карта: города — узлы, дороги — рёбра, расстояния — веса
- Электрическая цепь: компоненты — это узлы, провода — рёбра, сопротивление — вес
- Интернет: веб-сайты — это узлы, ссылки — рёбра, трафик — вес
- Транспортная сеть: станции — это узлы, маршруты — рёбра, тарифы — веса
| Сценарии | Другие структуры | Структура графа |
|---|---|---|
| Социальные отношения | Сложно выражать сложные отношения | Естественно выражает связи «многие ко многим» |
| Планирование путей | Требует сложных структур данных | Интуитивно представляет сети и пути |
| Отношения зависимостей | Сложно представить циклические зависимости | Легко обрабатывает сложные зависимости |
| Анализ сетей | Не может выразить топологию сети | Идеально описывает структуру сети |
Базовая терминология графов
| Термин | определение | Аналогия из жизни | Символьное представление |
|---|---|---|---|
| Вершина | Базовая единица в графе | Люди в социальных сетях | V, u, v |
| Edge | Линия, соединяющая две вершины | Связь между двумя людьми | E, (u,v) |
| Степень | Количество рёбер, соединённых с вершиной | Количество друзей у человека | deg(v) |
| Путь | Последовательность вершин | Маршрут из A в B | v₁→v₂→…→vₙ |
| Цикл | Путь с совпадающими начальной и конечной точками | Начать из дома и в конце вернуться домой | v₁→v₂→…→v₁ |
| Связный | Между любыми двумя точками существует путь | Каждый может соединиться с каждым | |
| Вес | Числовая характеристика ребра | Расстояние между двумя городами | w(u,v) |
Классификация графов

| Критерии классификации | Type | Особенности | сценарии применения |
|---|---|---|---|
| Направленность | Неориентированный граф | Рёбра не имеют направления | Дружеские связи, дорожные сети |
| Ориентированный граф | Рёбра имеют направление | Отношения подписки, рабочие процессы | |
| Вес | Невзвешенный граф | Все рёбра имеют одинаковый вес | Связи в социальных сетях |
| Взвешенный граф | Рёбра имеют разные веса | Расстояние на карте, сетевой трафик | |
| Подключение | Связный | Любые две точки достижимы | Транспортная сеть |
| Несвязный граф | Есть изолированные вершины | Социальные группы | |
| Цикл | Ациклический граф | Нет циклов | Зависимости задач, семейные деревья |
| Циклический граф | Содержит циклы | Дорожная сеть |
Методы представления графов
матрица смежности
| Особенности | Описание | Временная сложность | Пространственная сложность |
|---|---|---|---|
| Способ хранения | двумерная матрица | ||
| проверка существования ребра | matrix[i][j] != 0 |
O(1) | |
| добавление ребра | matrix[i][j] = weight |
O(1) | |
| удаление ребра | matrix[i][j] = 0 |
O(1) | |
| обход смежных вершин | сканирование строки/столбца | O(V) | |
| использование памяти | матрица V×V | O(V²) |
список смежности
| Особенности | Описание | Временная сложность | Пространственная сложность |
|---|---|---|---|
| Способ хранения | массив + связанный список | ||
| проверка существования ребра | Поиск в связанном списке | O(deg(v)) | |
| добавление ребра | Добавление в связанный список | O(1) | |
| удаление ребра | Удаление из связанного списка | O(deg(v)) | |
| обход смежных вершин | обход связного списка | O(deg(v)) | |
| использование памяти | Массив вершин + связный список рёбер | O(V+E) |
Основные понятия графов
графGСостоит из двух множеств:
- Множество вершин V (Vertex Set): множество всех вершин графа.
- Множество рёбер E (Edge Set): множество линий, соединяющих эти точки. Ребро определяется двумя вершинами, которые оно соединяет
(u, v)Представляет.
Пример
# Вершины: Alice, Bob, Charlie, Diana
# Рёбра: представляют дружеские отношения между ними
social_graph = {
'Alice': ['Bob', 'Charlie'], # Алиса дружит с Бобом и Чарли
'Bob': ['Alice', 'Charlie', 'Diana'],
'Charlie': ['Alice', 'Bob'],
'Diana': ['Bob']
}
print(fВершины (пользователи): {list(social_graph.keys())})
print(fДрузья Алисы (рёбра): {social_graph['Alice']})
Вывод:
顶点(用户): ['Alice', 'Bob', 'Charlie', 'Diana'] Alice 的好友(边): ['Bob', 'Charlie']
Классификация графов и важные понятия
Графы можно разделить на несколько типов в зависимости от свойств их рёбер; понимание этого — основа для освоения теории графов.
Неориентированный граф против ориентированного графа
| Type | Характеристики рёбер (Edge) | аналогия из жизни | Пример |
|---|---|---|---|
| Неориентированный граф | Рёбра не имеют направления,(A, B)Означает, что A и B взаимно связаны. |
двусторонняя дружба: если Алиса — друг Боба, то Боб тоже должен быть другом Алисы. | Дружеские связи в социальных сетях, соединения в цепях. |
| Ориентированный граф | рёбра имеют направление,A -> BПредставляет одностороннюю связь из A в B. |
Подписки в Weibo: вы можете подписаться на кого-то, но другой человек может не подписаться на вас в ответ. | Веб-гиперссылки, зависимости задач, дороги с односторонним движением. |

взвешенный граф
В взвешенном графе каждому ребру присваивается числовое значение (вес), которое может обозначать расстояние, стоимость, время или силу связи.
Пример
weighted_graph = {
'Пекин': {('Шанхай', 1200), ('Тяньцзинь', 100)}, # Расстояние от Пекина до Шанхая составляет 1200, до Тяньцзиня — 100
'Шанхай': {('Пекин', 1200), ('Ханчжоу', 200)},
'Тяньцзинь': {('Пекин', 100)},
'Ханчжоу': {('Шанхай', 200)}
}
ключевые термины
- степень (Degree): количество рёбер, соединённых с вершиной. В ориентированном графе она делится наполустепень захода(количество рёбер, входящих в вершину) иполустепень исхода(количество рёбер, исходящих из вершины).
- путь (Path): последовательность рёбер, проходимых от одной вершины к другой. Например,
A -> B -> C。 - цикл/контур (Cycle): путь, начальная и конечная точки которого являются одной и той же вершиной.
- Связный граф: в неориентированном графе между любыми двумя вершинами существует путь.
- Сильно связный граф: в ориентированном графе между любыми двумя вершинами существует путь.двунаправленныйпуть.
Способы хранения графа
Как представить граф в компьютере? Существуют в основном два основных способа.
матрица смежности
Использовать двумерный массив (матрицу)matrixдля представления графа.matrix[i][j]Значение представляет вершинуiк вершинеjРасположение рёбер.
- Для неориентированных графов матрица симметрична.
- Для взвешенного графа элементы матрицы хранят веса (используя специальные значения, такие как
0или∞Означает отсутствие ребра). - Преимущества: проверка наличия ребра между любыми двумя вершинами выполняется очень быстро (
O(1))。 - Недостатки: занимает много места (
O(V^2)), но он тратит место для «разреженных графов» с небольшим числом рёбер.
Пример
# Вершины: 0-A, 1-B, 2-C
# Рёбра: A-B, A-C
V = 3 # Количество вершин
adj_matrix = [[0] * V for _ in range(V)]
# Добавить ребро A-B (0-1)
adj_matrix[0][1] = 1
adj_matrix[1][0] = 1 # Для неориентированного графа нужно задать симметричные позиции
# Добавить ребро A-C (0-2)
adj_matrix[0][2] = 1
adj_matrix[2][0] = 1
print("Матрица смежности:")
for row in adj_matrix:
print(row)
# Вывод:
# [0, 1, 1]
# [1, 0, 0]
# [1, 0, 0]
список смежности
Храните список (связный список, массив и т. д.) для каждой вершины, записывая все вершины (и веса), непосредственно соединённые с ней.
- Преимущества: высокая эффективность использования памяти (
O(V + E)), особенно подходит для разреженных графов. Позволяет быстро находить всех соседей вершины. - Недостатки: проверка наличия ребра между любыми двумя вершинами медленнее (
O(degree(V)))。
Пример
adj_list = {
'A': ['B', 'C'], # A соединяется с B и C
'B': ['A'], # B соединяется с A
'C': ['A'] # C соединяется с A
}
print("Список смежности:")
for vertex, neighbors in adj_list.items():
print(f"{vertex}: {neighbors}")
Алгоритмы обхода графа
Обход — это основа алгоритмов на графах; он означает систематическое посещение каждой вершины графа.
Существуют в основном две стратегии:
Поиск в ширину
Поиск в ширину (BFS) похож на «распространение волны воды»: начиная с начальной точки, он сначала посещает всех непосредственных соседей, затем соседей соседей и так далее. Для реализации используетсяочередь.
Шаги алгоритма:
- Поместите начальную точку в очередь и отметьте её как посещённую.
- Когда очередь не пуста:
a. Извлеките из очереди переднюю вершину
v. b. Посетитеvвсех непосещённых соседей этой вершины, поместите их в очередь и отметьте как посещённые. - Повторите шаг 2.
Пример
def bfs(graph, start):
"""Использует BFS для обхода графа, возвращает порядок посещения"""
visited = set([start]) # Запись посещённых вершин
queue = deque([start]) # Инициализация очереди
result = [] # Сохранить порядок посещения
while queue:
vertex = queue.popleft()
result.append(vertex)
# Обойти соседей текущей вершины
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# Тестовые данные
test_graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print("Порядок обхода BFS (начиная с A):", bfs(test_graph, 'A'))
# Вывод может быть: ['A', 'B', 'C', 'D', 'E', 'F']
Поиск в глубину
Поиск в глубину (DFS) похож на «проход по лабиринту»: он выбирает один путь, идёт до конца, затем возвращается назад и выбирает другой путь. Он используетСтек(или рекурсию) для реализации.
Шаги рекурсивного алгоритма:
- от вершины
vStart, пометить как посещённую - for
vкаждого непосещённого соседаu: a. Рекурсивный вызовDFS(u)。
Пример
"""Реализация DFS с помощью рекурсии"""
if visited is None:
visited = set()
if result is None:
result = []
visited.add(vertex)
result.append(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, result)
return result
print("Порядок обхода DFS (начиная с A):", dfs_recursive(test_graph, 'A'))
# Вывод может быть: ['A', 'B', 'D', 'E', 'F', 'C']
Сравнение алгоритмов обхода графов:

Классические прикладные и алгоритмические задачи:
Освоив представление и обход графов, вы сможете решать следующие классические задачи:
Кратчайший путь: найти кратчайший маршрут движения между двумя точками.
- Алгоритм Дейкстры: применим к графам снеотрицательными весами.
- Алгоритм Флойда: вычислить кратчайший путь между любыми двумя вершинами.
Минимальное остовное дерево: при условии обеспечения связности всех вершин выбрать множество рёбер с наименьшим суммарным весом (например, прокладка самой дешёвой оптоволоконной сети для нескольких деревень).
- Алгоритм Прима
- Алгоритм Краскала
Топологическая сортировка: линейно упорядочить вершины ориентированного ациклического графа (DAG) так, чтобы для любого ориентированного ребра
u->v,uв сортировке все упорядоченыvперед (например, составлением порядка изучения курсов).