1. Теория графов: основные понятия

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

Граф - это математическая структура, представляющая собой множество вершин (узлов) и множество ребер (связей) между ними.

Основные термины:

1. Вершина (Node/Vertex) - фундаментальная единица графа
2. Ребро (Edge) - связь между двумя вершинами
3. Смежные вершины - вершины, соединенные ребром
4. Степень вершины - количество инцидентных ей ребер
5. Путь - последовательность вершин, соединенных ребрами
6. Цикл - путь, начинающийся и заканчивающийся в одной вершине
7. Взвешенный граф - граф, где ребрам присвоены числовые значения (веса)
8. Ориентированный граф - граф, где ребра имеют направление
9. Неориентированный граф - граф без направлений у ребер

Типы графов:

• Связный граф - между любыми двумя вершинами существует путь
• Полный граф - каждая вершина соединена со всеми остальными
• Дерево - связный граф без циклов
• Двудольный граф - вершины можно разделить на два множества

2. Представление графов в Python

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

class GraphAdjacencyMatrix:
    def __init__(self, num_vertices):
        self.num_vertices = num_vertices
        # Создаем матрицу num_vertices x num_vertices, заполненную нулями
        self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
    
    def add_edge(self, v1, v2, weight=1, directed=False):
        """Добавление ребра между вершинами v1 и v2"""
        self.matrix[v1][v2] = weight
        if not directed:  # Если граф неориентированный
            self.matrix[v2][v1] = weight
    
    def remove_edge(self, v1, v2, directed=False):
        """Удаление ребра между вершинами v1 и v2"""
        self.matrix[v1][v2] = 0
        if not directed:
            self.matrix[v2][v1] = 0
    
    def get_adjacent_vertices(self, vertex):
        """Получение смежных вершин"""
        adjacent = []
        for i in range(self.num_vertices):
            if self.matrix[vertex][i] != 0:
                adjacent.append((i, self.matrix[vertex][i]))
        return adjacent
    
    def print_matrix(self):
        """Вывод матрицы смежности"""
        for row in self.matrix:
            print(' '.join(map(str, row)))

# Пример использования
print("=== Матрица смежности ===")
graph_matrix = GraphAdjacencyMatrix(5)
graph_matrix.add_edge(0, 1, 3)
graph_matrix.add_edge(0, 4, 7)
graph_matrix.add_edge(1, 2, 2)
graph_matrix.add_edge(1, 3, 8)
graph_matrix.add_edge(3, 4, 1)

print("Матрица смежности:")
graph_matrix.print_matrix()
print(f"Смежные с вершиной 1: {graph_matrix.get_adjacent_vertices(1)}")

2.2. Список смежности

from collections import defaultdict

class GraphAdjacencyList:
    def __init__(self, directed=False):
        self.graph = defaultdict(list)
        self.directed = directed
        self.vertices = set()
    
    def add_edge(self, v1, v2, weight=1):
        """Добавление ребра между вершинами"""
        self.graph[v1].append((v2, weight))
        self.vertices.add(v1)
        self.vertices.add(v2)
        
        if not self.directed:  # Если граф неориентированный
            self.graph[v2].append((v1, weight))
    
    def remove_edge(self, v1, v2):
        """Удаление ребра"""
        self.graph[v1] = [(node, w) for node, w in self.graph[v1] if node != v2]
        if not self.directed:
            self.graph[v2] = [(node, w) for node, w in self.graph[v2] if node != v1]
    
    def get_vertices(self):
        """Получение всех вершин"""
        return list(self.vertices)
    
    def get_adjacent_vertices(self, vertex):
        """Получение смежных вершин"""
        return self.graph.get(vertex, [])
    
    def print_graph(self):
        """Вывод графа"""
        for vertex in sorted(self.graph.keys()):
            connections = ', '.join([f"{node}({w})" for node, w in self.graph[vertex]])
            print(f"{vertex}: {connections}")

print("\n=== Список смежности ===")
graph_list = GraphAdjacencyList(directed=False)
graph_list.add_edge('A', 'B', 5)
graph_list.add_edge('A', 'C', 3)
graph_list.add_edge('B', 'D', 2)
graph_list.add_edge('C', 'D', 7)
graph_list.add_edge('D', 'E', 1)

print("Граф в виде списка смежности:")
graph_list.print_graph()
print(f"Все вершины: {graph_list.get_vertices()}")
print(f"Смежные с 'B': {graph_list.get_adjacent_vertices('B')}")

3. Алгоритмы обхода графов

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

from collections import deque

def bfs(graph, start_vertex):
    """Поиск в ширину (Breadth-First Search)"""
    visited = set()
    queue = deque([start_vertex])
    result = []
    
    visited.add(start_vertex)
    
    while queue:
        vertex = queue.popleft()
        result.append(vertex)
        
        for neighbor, _ in graph.get_adjacent_vertices(vertex):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

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

def dfs_recursive(graph, vertex, visited=None, result=None):
    """Рекурсивный поиск в глубину (Depth-First Search)"""
    if visited is None:
        visited = set()
    if result is None:
        result = []
    
    visited.add(vertex)
    result.append(vertex)
    
    for neighbor, _ in graph.get_adjacent_vertices(vertex):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, result)
    
    return result

def dfs_iterative(graph, start_vertex):
    """Итеративный поиск в глубину"""
    visited = set()
    stack = [start_vertex]
    result = []
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            result.append(vertex)
            
            # Добавляем соседей в стек
            neighbors = graph.get_adjacent_vertices(vertex)
            # Для сохранения порядка, добавляем в обратном порядке
            for neighbor, _ in reversed(neighbors):
                if neighbor not in visited:
                    stack.append(neighbor)
    
    return result

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

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

import heapq

def dijkstra(graph, start_vertex):
    """Алгоритм Дейкстры для поиска кратчайших путей"""
    distances = {vertex: float('inf') for vertex in graph.get_vertices()}
    distances[start_vertex] = 0
    previous_vertices = {vertex: None for vertex in graph.get_vertices()}
    
    priority_queue = [(0, start_vertex)]
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        for neighbor, weight in graph.get_adjacent_vertices(current_vertex):
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_vertices[neighbor] = current_vertex
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances, previous_vertices

def get_shortest_path(previous_vertices, target_vertex):
    """Восстановление кратчайшего пути"""
    path = []
    current_vertex = target_vertex
    
    while current_vertex is not None:
        path.append(current_vertex)
        current_vertex = previous_vertices[current_vertex]
    
    return path[::-1]

4.2. Проверка на циклы

def has_cycle_dfs(graph, vertex, visited, parent):
    """Проверка наличия цикла в графе (для неориентированных графов)"""
    visited.add(vertex)
    
    for neighbor, _ in graph.get_adjacent_vertices(vertex):
        if neighbor not in visited:
            if has_cycle_dfs(graph, neighbor, visited, vertex):
                return True
        elif neighbor != parent:
            return True
    
    return False

def has_cycle(graph):
    """Основная функция проверки на циклы"""
    visited = set()
    
    for vertex in graph.get_vertices():
        if vertex not in visited:
            if has_cycle_dfs(graph, vertex, visited, -1):
                return True
    
    return False

5. Пример практического применения

class SocialNetworkGraph:
    """Пример графа для социальной сети"""
    def __init__(self):
        self.graph = GraphAdjacencyList(directed=False)
    
    def add_friendship(self, person1, person2, closeness=1):
        """Добавление дружбы между людьми"""
        self.graph.add_edge(person1, person2, closeness)
    
    def find_common_friends(self, person1, person2):
        """Поиск общих друзей"""
        friends1 = {friend for friend, _ in self.graph.get_adjacent_vertices(person1)}
        friends2 = {friend for friend, _ in self.graph.get_adjacent_vertices(person2)}
        return friends1.intersection(friends2)
    
    def recommend_friends(self, person):
        """Рекомендация друзей по принципу 'друзья друзей'"""
        recommendations = {}
        friends = {friend for friend, _ in self.graph.get_adjacent_vertices(person)}
        
        for friend in friends:
            for friend_of_friend, closeness in self.graph.get_adjacent_vertices(friend):
                if friend_of_friend != person and friend_of_friend not in friends:
                    if friend_of_friend not in recommendations:
                        recommendations[friend_of_friend] = 0
                    recommendations[friend_of_friend] += closeness
        
        return sorted(recommendations.items(), key=lambda x: x[1], reverse=True)

# Демонстрация работы
print("\n=== Социальная сеть ===")
social_net = SocialNetworkGraph()

# Добавляем друзей
social_net.add_friendship("Алексей", "Мария", 5)
social_net.add_friendship("Алексей", "Иван", 3)
social_net.add_friendship("Мария", "Елена", 4)
social_net.add_friendship("Иван", "Елена", 2)
social_net.add_friendship("Елена", "Дмитрий", 1)
social_net.add_friendship("Дмитрий", "Ольга", 6)

print("Граф социальной сети:")
social_net.graph.print_graph()

print(f"\nОбщие друзья Алексея и Елены: {social_net.find_common_friends('Алексей', 'Елена')}")
print(f"Рекомендации для Алексея: {social_net.recommend_friends('Алексей')}")

# Применяем алгоритмы
print(f"\nBFS обход начиная с 'Алексей': {bfs(social_net.graph, 'Алексей')}")
print(f"DFS обход начиная с 'Алексей': {dfs_iterative(social_net.graph, 'Алексей')}")

# Алгоритм Дейкстры для поиска "ближайших" друзей
distances, previous = dijkstra(social_net.graph, 'Алексей')
print(f"\nРасстояния от Алексея до других: {distances}")
print(f"Кратчайший путь к Ольге: {get_shortest_path(previous, 'Ольга')}")

6. Упражнения для практики

1. Реализуйте топологическую сортировку для ориентированного ациклического графа
2. Найдите все компоненты связности в неориентированном графе
3. Определите, является ли граф двудольным
4. Реализуйте алгоритм Прима для поиска минимального остовного дерева
5. Найдите эйлеров путь в графе (если существует)

7. Полезные библиотеки для работы с графами

• NetworkX - комплексная библиотека для работы с графами
• igraph - высокопроизводительная библиотека
• Graph-tool - эффективная библиотека на C++ с Python интерфейсом

# Пример установки NetworkX
# pip install networkx matplotlib

import networkx as nx
import matplotlib.pyplot as plt

def visualize_graph():
    """Визуализация графа с помощью NetworkX"""
    G = nx.Graph()
    
    # Добавляем вершины и ребра
    G.add_edge('A', 'B', weight=5)
    G.add_edge('A', 'C', weight=3)
    G.add_edge('B', 'D', weight=2)
    G.add_edge('C', 'D', weight=7)
    G.add_edge('D', 'E', weight=1)
    
    # Рисуем граф
    pos = nx.spring_layout(G)
    nx.draw(G, pos, with_labels=True, node_color='lightblue', 
            node_size=2000, font_size=16, font_weight='bold')
    
    # Добавляем веса ребер
    labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)
    
    plt.title("Визуализация графа")
    plt.show()

# Запустите для визуализации:
# visualize_graph()

Заключение

Графы - мощная структура данных для представления сложных взаимосвязей. Понимание основных алгоритмов работы с графами важно для решения многих практических задач:

• Социальные сети и рекомендательные системы
• Маршрутизация в сетях и навигация
• Зависимости в программных проектах
• Биоинформатика и анализ данных

Начните с простых реализаций на чистом Python, чтобы понять основы, а затем переходите к специализированным библиотекам для сложных задач.