6.2. Графы и табличные модели

Графы и их элементы

Граф — это совокупность вершин (узлов) и соединяющих их рёбер.

Основные понятия:

Понятие	Описание
Вершина (узел)	Элемент графа, обозначающий объект
Ребро (дуга)	Связь между двумя вершинами
Путь	Последовательность рёбер, соединяющая вершины
Цикл	Замкнутый путь (начало = конец)
Степень вершины	Количество рёбер, инцидентных вершине

Виды графов

Ориентированный граф (орграф):

Рёбра имеют направление, обозначаемое стрелками. Используется для представления односторонних связей.

Пример: Схема дорог с односторонним движением.

Неориентированный граф:

Рёбра не имеют направления. Связь между вершинами двусторонняя.

Пример: Схема метро, социальные связи.

Взвешенный граф:

Каждому ребру присвоено число — вес (расстояние, стоимость, время).

Пример: Карта дорог с указанием расстояний между городами.

Матрица смежности

Матрица смежности — это таблица, которая описывает связи между вершинами графа.

Если в графе N вершин, матрица имеет размер N×N. Элемент a_ij = 1, если есть ребро между вершинами i и j, иначе 0.

Пример матрицы смежности для 3 вершин:

	A	B	C
A	0	1	1
B	1	0	0
C	1	0	0

Этот граф имеет рёбра: A-B, A-C.

Деревья решений

Дерево — это связный граф без циклов. В дереве между любыми двумя вершинами существует единственный путь.

Дерево решений — граф, отображающий последовательность вариантов выбора.

Корень дерева — начальная вершина, листья — вершины без потомков.

Свойства деревьев:

• Количество рёбер = количество вершин − 1
• Между любыми двумя вершинами — ровно один путь
• Добавление любого ребра создаёт цикл
• Удаление любого ребра разрывает связность

Алгоритмы на графах

Обход в ширину (BFS)

Обходит граф «по уровням»: сначала все соседи начальной вершины, затем их соседи и т.д.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Применение: поиск кратчайшего пути в невзвешенном графе, проверка связности.

Обход в глубину (DFS)

Идёт «вглубь» по графу, пока не упрётся в тупик, затем возвращается.

def dfs(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    order = [vertex]
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            order.extend(dfs(graph, neighbor, visited))
    return order

Применение: поиск циклов, проверка двусвязности, топологическая сортировка.

Алгоритм Дейкстры (кратчайший путь)

Находит кратчайший путь от одной вершины до всех остальных во взвешенном графе с неотрицательными весами.

import heapq

def dijkstra(graph, start):
    distances = {v: float('inf') for v in graph}
    distances[start] = 0
    heap = [(0, start)]

    while heap:
        dist, vertex = heapq.heappop(heap)
        if dist > distances[vertex]:
            continue
        for neighbor, weight in graph[vertex]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
    return distances

Применение: навигаторы, маршрутизация сетевого трафика.

Практические задания