Что такое граф?

Граф (Graph)

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

Основные компоненты

• Вершина (Node/Vertex) — узел графа (может быть город, человек, веб-страница)
• Ребро (Edge) — связь между двумя вершинами
• Вес ребра — стоимость связи (расстояние, время, цена)

Типы графов

1. Неориентированный граф (Undirected Graph)

# Рёбра работают в обе стороны
# Пример: дружба в социальной сети (если A друг B, то B друг A)

class UndirectedGraph:
    def __init__(self):
        self.graph = {}  # Словарь смежности
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, vertex1, vertex2):
        if vertex1 not in self.graph:
            self.add_vertex(vertex1)
        if vertex2 not in self.graph:
            self.add_vertex(vertex2)
        
        self.graph[vertex1].append(vertex2)
        self.graph[vertex2].append(vertex1)

# Использование
graph = UndirectedGraph()
graph.add_edge('Alice', 'Bob')
graph.add_edge('Bob', 'Charlie')

2. Ориентированный граф (Directed Graph)

class DirectedGraph:
    def __init__(self):
        self.graph = {}
    
    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []
    
    def add_edge(self, from_vertex, to_vertex):
        if from_vertex not in self.graph:
            self.add_vertex(from_vertex)
        if to_vertex not in self.graph:
            self.add_vertex(to_vertex)
        
        self.graph[from_vertex].append(to_vertex)

# Использование
graph = DirectedGraph()
graph.add_edge('Alice', 'Bob')
graph.add_edge('Bob', 'Charlie')

3. Взвешенный граф (Weighted Graph)

class WeightedGraph:
    def __init__(self):
        self.graph = {}
    
    def add_edge(self, from_vertex, to_vertex, weight):
        if from_vertex not in self.graph:
            self.graph[from_vertex] = []
        if to_vertex not in self.graph:
            self.graph[to_vertex] = []
        
        self.graph[from_vertex].append((to_vertex, weight))
        self.graph[to_vertex].append((from_vertex, weight))

# Использование
graph = WeightedGraph()
graph.add_edge('A', 'B', 4)
graph.add_edge('B', 'C', 2)

Основные алгоритмы обхода

Поиск в ширину (BFS)

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Использование
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

bfs(graph, 'A')

Поиск в глубину (DFS)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start, end=' ')
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Использование
dfs(graph, 'A')

Алгоритм Dijkstra для кратчайшего пути

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

# Использование
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}

result = dijkstra(graph, 'A')
print(result)

Обнаружение цикла

def has_cycle(graph):
    visited = set()
    rec_stack = set()
    
    def dfs(vertex):
        visited.add(vertex)
        rec_stack.add(vertex)
        
        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                if dfs(neighbor):
                    return True
            elif neighbor in rec_stack:
                return True
        
        rec_stack.remove(vertex)
        return False
    
    for vertex in graph:
        if vertex not in visited:
            if dfs(vertex):
                return True
    
    return False

# Использование
graph = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(has_cycle(graph))

Представления графа

# Матрица смежности
adjacency_matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

# Список смежности (более эффективно)
adjacency_list = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Список рёбер
edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')]

Ключевые моменты

• Вершина — узел, ребро — связь между ними
• Неориентированный граф — рёбра работают в обе стороны
• Ориентированный граф — рёбра имеют направление
• Взвешенный граф — рёбра имеют вес (стоимость)
• BFS — поиск в ширину (уровень за уровнем)
• DFS — поиск в глубину (рекурсивный)
• Dijkstra — находит кратчайший путь в взвешенном графе
• Список смежности — более эффективен для разреженных графов