Графы

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

• Социальных сетей

• Транспортных систем

• Компьютерных сетей

• Зависимостей между задачами

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

• Вершина (узел) - основной элемент графа (может содержать ключ и данные)

• Ребро - связь между вершинами (может быть направленным/ненаправленным, взвешенным)

• Степень вершины - количество рёбер, инцидентных вершине

• Путь - последовательность вершин, соединённых рёбрами

Типы графов:

1. Ориентированные (digraph) - рёбра имеют направление (пример: Twitter)

2. Неориентированные - рёбра без направления (пример: Facebook)

3. Взвешенные - рёбра имеют числовые значения (вес)

4. Полные - каждая вершина соединена со всеми другими

Сложность операций:

*V - количество вершин, E - количество рёбер

Улучшенная реализация графа (список смежности):

class Vertex:
    def __init__(self, key, payload=None):
        self.key = key
        self.payload = payload  # Дополнительные данные
        self.connections = {}  # {vertex: weight}
    
    def add_neighbor(self, neighbor, weight=0):
        """Добавление соседа с весом"""
        self.connections[neighbor] = weight
    
    def get_connections(self):
        """Получение всех соседей"""
        return self.connections.keys()
    
    def get_weight(self, neighbor):
        """Получение веса ребра"""
        return self.connections.get(neighbor)
    
    def __str__(self):
        """Строковое представление"""
        return f"{self.key} -> {[x.key for x in self.connections]}"

class Graph:
    def __init__(self, directed=False):
        self.vertices = {}
        self.directed = directed  # Ориентированный/неориентированный
    
    def add_vertex(self, key, payload=None):
        """Добавление вершины"""
        if key not in self.vertices:
            self.vertices[key] = Vertex(key, payload)
    
    def get_vertex(self, key):
        """Получение вершины по ключу"""
        return self.vertices.get(key)
    
    def add_edge(self, from_key, to_key, weight=0):
        """Добавление ребра"""
        if from_key not in self.vertices:
            self.add_vertex(from_key)
        if to_key not in self.vertices:
            self.add_vertex(to_key)
        
        self.vertices[from_key].add_neighbor(self.vertices[to_key], weight)
        if not self.directed:  # Для неориентированного графа добавляем обратное ребро
            self.vertices[to_key].add_neighbor(self.vertices[from_key], weight)
    
    def __iter__(self):
        """Итерация по вершинам графа"""
        return iter(self.vertices.values())
    
    def __contains__(self, key):
        """Проверка наличия вершины"""
        return key in self.vertices
    
    def __str__(self):
        """Строковое представление графа"""
        return '\n'.join(str(v) for v in self)

# Пример использования
g = Graph(directed=False)
g.add_vertex('A')
g.add_vertex('B')
g.add_vertex('C')
g.add_edge('A', 'B', 5)
g.add_edge('B', 'C', 3)
g.add_edge('A', 'C', 1)

print("Граф:")
print(g)

print("\nСоседи вершины A:")
for neighbor in g.get_vertex('A').get_connections():
    print(f"{neighbor.key} (вес: {g.get_vertex('A').get_weight(neighbor)})")