Структура теории графов

В информатике графы широко используются для моделирования социальных сетей (пользователи — узлы, дружеские связи — рёбра), веб-ссылок (веб-страницы — узлы, гиперссылки — рёбра), коммуникационных сетей и даже задач планирования маршрутов.

ГрафЭто как граф отношений социальной сети:

  • Узел (вершина): каждый человек в социальной сети
  • Ребро: отношения между людьми (друзья, подписки и т. д.)
  • Вес: сила отношений (близость, частота взаимодействия и т. д.)

Представьте транспортную сеть в вашем городе: различные места (такие как дом, школа, торговый центр) являютсяточками, дороги, соединяющие эти места, являютсялиниями. Граф (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) похож на «распространение волны воды»: начиная с начальной точки, он сначала посещает всех непосредственных соседей, затем соседей соседей и так далее. Для реализации используетсяочередь.

Шаги алгоритма:

  1. Поместите начальную точку в очередь и отметьте её как посещённую.
  2. Когда очередь не пуста: a. Извлеките из очереди переднюю вершинуv. b. Посетитеvвсех непосещённых соседей этой вершины, поместите их в очередь и отметьте как посещённые.
  3. Повторите шаг 2.

Пример

from collections import deque

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) похож на «проход по лабиринту»: он выбирает один путь, идёт до конца, затем возвращается назад и выбирает другой путь. Он используетСтек(или рекурсию) для реализации.

Шаги рекурсивного алгоритма:

  1. от вершиныvStart, пометить как посещённую
  2. forvкаждого непосещённого соседаu: a. Рекурсивный вызовDFS(u)。

Пример

def dfs_recursive(graph, vertex, visited=None, result=None):
    """Реализация 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']

Сравнение алгоритмов обхода графов:


Классические прикладные и алгоритмические задачи:

Освоив представление и обход графов, вы сможете решать следующие классические задачи:

  1. Кратчайший путь: найти кратчайший маршрут движения между двумя точками.

    • Алгоритм Дейкстры: применим к графам снеотрицательными весами.
    • Алгоритм Флойда: вычислить кратчайший путь между любыми двумя вершинами.
  2. Минимальное остовное дерево: при условии обеспечения связности всех вершин выбрать множество рёбер с наименьшим суммарным весом (например, прокладка самой дешёвой оптоволоконной сети для нескольких деревень).

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

Другие расширения