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

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

В конце статьи представлен перечень основных терминов, которые вы можете встретить в задачах по графам
Типы графов
1) Графы бывают ориентированные (направленные) и неориентированные (ненаправленные).

Ориентированный граф характеризует связь вершин только в одном направлении. Обратный граф может быть, но он должен явно указан.
В неориентированном графе по любому ребру можно пройти в обе стороны.

2) Рёбра графов могут иметь веса, тогда граф называется взвешенным.

3) Циклический граф если можно стартовать в некоторой вершине и вернуться в неё после перемещения по рёбрам, не проходя дважды по одному ребру. Ациклический граф, если в нём нет циклов (если граф при этом неориентированный и связный, он называется «дерево». Они разбираются отдельно в статье ниже).
Представления графов
Два являются наиболее часто используемыми представлениями графа являются:

1. Матрица смежности - представляет собой двумерный массив размером V x V, где V — количество вершин в графе. В пересечении матрицы записывается 1, если существует ребро между вершинами, и записывается 0, если его нет. Матрица смежности для неориентированного графа всегда симметрична. Матрица смежности также используется для представления взвешенных графов, где на пересечении вместо 1 указывается вес ребра.

2. Список смежности - используется массив списков. Размер массива равен количеству вершин. Элемент array[i] представляет собой список вершин, смежных с i -й вершиной. Это представление также можно использовать для представления взвешенного графа. Веса ребер могут быть представлены в виде списков пар.

В Матрице смежности легко обрабатывать информацию о ребрах, но при добавлении вершины занимает больше времени O(n^2). Удаление ребра занимает O(1) времени. Вычисление соседних вершин занимает O(n).

В Списке смежности добавление вершины производится быстрее. Вычисление всех соседей вершины занимает оптимальное время. Поиск ребра между вершинами занимает большее время O(n)
Матрица смежности
Список смежности
Пример класса для создания списков смежности графов 

from dataclasses import dataclass
from typing import ClassVar


@dataclass
class AdjNode:
    vertex: int
    next: ClassVar = None


@dataclass
class Graph:
    vertices: int
    graph: ClassVar = []

    def __post_init__(self):
        self.graph = [None] * vertices

    def add_edge(self, src, dest):
        '''Добавление ребра в неориентированный граф'''
        node = AdjNode(dest)
        node.next = self.graph[src]
        self.graph[src] = node
        # Добавление исходного узла к целевому
        node = AdjNode(src)
        node.next = self.graph[dest]
        self.graph[dest] = node

    def print_graph(self):
        '''Вывод графа'''
        for i in range(self.vertices):
            print(f'Список смежности вершины {i}\n', end='')
            temp = self.graph[i]
            while temp:
                print(" -> {}".format(temp.vertex), end="")
                temp = temp.next
            print(" \n")


if __name__ == "__main__":
    vertices = 5
    graph = Graph(vertices)
    graph.add_edge(0, 1)
    graph.add_edge(0, 4)
    graph.add_edge(1, 2)
    graph.add_edge(1, 3)
    graph.add_edge(1, 4)
    graph.add_edge(2, 3)
    graph.add_edge(3, 4)

    graph.print_graph()
Задача на поиск в ширину
Обход в ширину (или поиск) для графа аналогичен обходу в ширину дерева (статья деревья). Алгоритм ищет все соседние вершины у корня, далее переходит к поиску всех соседних вершин у каждой найденной. В отличие от деревьев, графы могут содержать циклы, поэтому возможен возврат к узлу. Чтобы избежать обработки узла повторно, используем вспомогательный логический массив посещений.

Например, на следующем графе начинаем обход с вершины 2. Дойдя до вершины 0, ищем все соседние с ней вершины. 2 также является смежной вершиной с 0. Если не будем отмечать посещенные вершины, то 2 будет обработана снова, и это станет зацикливанием.
Для вершины 2 -> 2 0 3 1
Обход в ширину
Временная сложность: O(V+E), где V — количество узлов, а E — количество ребер.
Расход памяти: O(V)

from collections import defaultdict
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class Graph:
    '''Класс ориентированного графа'''
    graph: ClassVar

    def __post_init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, start, finish):
        '''Добавления ребра к графу'''
        self.graph[start].append(finish)

    def BFS(self, vertex):
        '''Функция вывода обхода'''

        # Логический массив посещений
        visited = [False] * (max(self.graph) + 1)
        # очередь обхода BFS
        queue = []
        # добавление первого узла обхода
        queue.append(vertex)
        visited[vertex] = True

        while queue:
            vertex = queue.pop(0)
            print(vertex, end=' ')
            # Проход по соседним вершинам
            for i in self.graph[vertex]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True


if __name__ == '__main__':
    graph = Graph()
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    vertex: int = 3
    print(f"Обход в ширину для стартового узла {vertex}")
    graph.BFS(vertex)
Задача на поиск в глубину
Обход в глубину (или поиск) для графа также аналогичен обходу в глубину дерева (статья деревья) . Алгоритм позволяет пройтись по ветке от корня до конца, далее перейти к другой ветке. В отличие от деревьев, графы могут содержать циклы, поэтому возможен возврат к узлу. Чтобы избежать обработки узла повторно, используем вспомогательный логический массив посещений.

Алгоритм начинается с корневого узла и исследует как можно дальше каждую ветвь перед возвратом.
Для вершины 2 -> 2 0 1 3
Обход в глубину
  • Временная сложность: O(V + E), где V — количество вершин, а E — количество ребер в графе.
  • Память: O(V), так как требуется дополнительный посещенный массив размера V. 

from collections import defaultdict
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class graphraph:
    '''Класс ориентированного графа'''
    graphraph: ClassVar

    def __post_init__(self):
        self.graphraph = defaultdict(list)

    def addEdgraphe(self, start, finish):
        '''Добавления ребра к графу'''
        self.graphraph[start].append(finish)

    def DFSUtil(self, v, visited):
        '''Функция вывода обхода'''

        visited.add(v)
        print(v, end=' ')

        for neigraphhbour in self.graphraph[v]:
            if neigraphhbour not in visited:
                self.DFSUtil(neigraphhbour, visited)

    def DFS(self, vertex):
        '''Функция рекурсии обхода'''

        visited = set()
        self.DFSUtil(vertex, visited)


if __name__ == '__main__':
    graph = graphraph()
    graph.addEdgraphe(0, 1)
    graph.addEdgraphe(0, 2)
    graph.addEdgraphe(1, 2)
    graph.addEdgraphe(2, 0)
    graph.addEdgraphe(2, 3)
    graph.addEdgraphe(3, 3)
    vertex: int = 2
    print(f"Обход в ширину для стартового узла {vertex}")
    graph.DFS(vertex)
Алгоритм кратчайшего пути Дейкстры
Алгоритм рассчитывает самое короткое расстояние от источника до каждой вершины. Рассмотрим график графа и рассчитаем самые короткие расстояния до всех вершин от источника 1
Временная сложность реализации — O(V^2).
Если входной граф представлен с помощью списка смежности , его можно сократить до O(E log V) с помощью двоичной кучи

import sys
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class Graph():
    vertices: int
    graph: ClassVar

    def __post_init__(self):
        self.graph = [[0 for column in range(self.vertices)]
                      for row in range(self.vertices)]

    def printSolution(self, dist):
        '''Вывод вершин'''
        print("Вершина \tРастояние до источника")
        for node in range(self.vertices):
            print(node+1, "\t", dist[node])

    def minDistance(self, dist, sptSet):
        '''Вычисление минимального расстояния'''
        min = sys.maxsize
        for u in range(self.vertices):
            if dist[u] < min and not(sptSet[u]):
                min = dist[u]
                min_index = u
        return min_index

    def dijkstra(self, src):
        '''Вычисление минимальны= маршрутов'''
        dist = [sys.maxsize] * self.vertices
        dist[src] = 0
        sptSet = [False] * self.vertices

        for cout in range(self.vertices):
            x = self.minDistance(dist, sptSet)
            sptSet[x] = True
            for y in range(self.vertices):
                if self.graph[x][y] > 0 and\
                   not(sptSet[y]) and \
                   dist[y] > dist[x] + self.graph[x][y]:

                    dist[y] = dist[x] + self.graph[x][y]
        self.printSolution(dist)


if __name__ == '__main__':
    graph = Graph(6)
    graph.graph = [[0, 3, 1, 3, 0, 0],
                   [3, 0, 4, 0, 0, 0],
                   [1, 4, 0, 0, 7, 5],
                   [3, 0, 0, 0, 0, 2],
                   [0, 0, 7, 0, 0, 4],
                   [0, 0, 5, 2, 4, 0]]

    graph.dijkstra(0)
Определить, есть ли цикл в ориентированном графе.
Для данного ориентированного графа проверьте, содержит ли граф цикл или нет. Ваша функция должна возвращать true, если данный граф содержит хотя бы один цикл, иначе возвращать false.

Циклом в графе называют ситуацию когда есть ребра, по которым можно вернуться из вершины старта, пройдя через другие вершины. Также может быть ребро, которое имеет выход и вход из одной вершины.
На графике есть 3 цикла

from collections import defaultdict
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class Graph():
    '''Класс ориентированного графа'''
    vertices: int
    graph: ClassVar

    def __post_init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, start, finish):
        '''Добавления ребра к графу'''
        self.graph[start].append(finish)

    def isCyclicUtil(self, v, visited, recStack):
        '''Поиск цикла'''

        visited[v] = True
        recStack[v] = True
        for neighbour in self.graph[v]:
            if not visited[neighbour]:
                if self.isCyclicUtil(neighbour, visited, recStack):
                    return True
            elif recStack[neighbour]:
                return True
        recStack[v] = False
        return False

    def isCyclic(self):
        '''Проверка всех путей на цикличность'''

        visited = [False] * (self.vertices + 1)
        recStack = [False] * (self.vertices + 1)
        for node in range(self.vertices):
            if not visited[node]:
                if self.isCyclicUtil(node, visited, recStack):
                    return True
        return False


if __name__ == '__main__':
    graph = Graph(4)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(2, 3)
    graph.addEdge(3, 3)
    if graph.isCyclic():
        print('График имеет цикл')
    else:
        print('График не имеет циклов')
Определить, есть ли цикл в неориентированном графе.
Для данного неориентированного графа проверьте, содержит ли граф цикл или нет. Ваша функция должна возвращать true, если данный граф содержит хотя бы один цикл, иначе возвращать false.

Для поиска цикла используется обход в глубину

from collections import defaultdict
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class Graph():
    '''Класс ориентированного графа'''
    vertices: int
    graph: ClassVar

    def __post_init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, start, finish):
        '''Добавления двух ребер к графу'''
        self.graph[start].append(finish)
        self.graph[finish].append(start)

    def isCyclicUtil(self, v, visited, parent):
        '''Поиск цикла'''
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                if(self.isCyclicUtil(i, visited, v)):
                    return True
            elif parent != i:
                return True
        return False

    def isCyclic(self):
        '''Проверка всех путей на цикличность'''
        visited = [False]*(self.vertices)
        for i in range(self.vertices):
            if not visited[i]:
                if(self.isCyclicUtil
                   (i, visited, -1)):
                    return True
        return False


if __name__ == "__main__":
    graph = Graph(5)
    graph.addEdge(1, 0)
    graph.addEdge(1, 2)
    graph.addEdge(2, 0)
    graph.addEdge(0, 3)
    graph.addEdge(3, 4)
    if graph.isCyclic():
        print("График имеет цикл")
    else:
        print("График не имеет циклов")
Найти топологическую сортировку вершин ориентированного графа
Топологическая сортировка для ориентированного ациклического графа (DAG) — это линейное упорядочение вершин, при котором для каждого направленного ребра uv вершина u предшествует v в упорядочении. Топологическая сортировка для графа невозможна, если граф не является DAG.

Например, топологическая сортировка следующего графа — «5 4 2 3 1 0». Для графа может быть более одной топологической сортировки. Например, другая топологическая сортировка следующего графа — «4 5 2 3 1 0». Первая вершина в топологической сортировке всегда является вершиной с нулевой степенью вхождения (вершина без входящих ребер). 


from collections import defaultdict
from dataclasses import dataclass
from typing import ClassVar


@dataclass
class Graph():
    '''Класс ориентированного графа'''
    vertices: int
    graph: ClassVar

    def __post_init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, start, finish):
        '''Добавления ребра к графу'''
        self.graph[start].append(finish)

    def topological_sort_util(self, v, visited, stack):
        visited[v] = True
        for i in self.graph[v]:
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        stack.append(v)

    def topologicalSort(self):
        '''Сортировка вершин'''
        visited = [False]*self.vertices
        stack = []

        for i in range(self.vertices):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        print(stack[::-1])


if __name__ == '__main__':
    graph = Graph(6)
    graph.addEdge(5, 2)
    graph.addEdge(5, 0)
    graph.addEdge(4, 0)
    graph.addEdge(4, 1)
    graph.addEdge(2, 3)
    graph.addEdge(3, 1)

    graph.topologicalSort()
Ключевые термины по теме граф
Вес (длина) ребра – это число или несколько чисел, которые интерпретируются по отношению к ребру как длина, пропускная способность.

Вес вершины – это число (действительное, целое или рациональное), поставленное в соответствие данной вершине.

Взвешенный граф – это граф, каждому ребру которого поставлен в соответствие его вес.

Вершины (узлы) графа – это множество точек, составляющих граф.

Замкнутый маршрут – это маршрут в графе, у которого начальная и конечная вершины совпадают.

Кратные ребра – это ребра, соединяющие одну и ту же пару вершин.

Маршрут в графе – это конечная чередующаяся последовательность смежных вершин и ребер, соединяющих эти вершины.

Матрица инцидентности – это двумерный массив, в котором указываются связи между инцидентными элементами графа (ребро и вершина).

Матрица смежности – это двумерный массив, значения элементов которого характеризуются смежностью вершин графа

Мультиграф – это граф, у которого любые две вершины соединены более чем одним ребром.

Неориентированный граф (неорграф) – это граф, у которого все ребра не ориентированы, то есть ребрам которого не задано направление.

Обход графа (поиск на графе) – это процесс систематического просмотра всех ребер или вершин графа с целью отыскания ребер или вершин, удовлетворяющих некоторому условию.

Ориентированный граф (орграф) – это граф, у которого все ребра ориентированы, то есть ребрам которого присвоено направление.

Открытый маршрут – это маршрут в графе, у которого начальная и конечная вершины различны.

Петля – это ребро, соединяющее вершину саму с собой.

Поиск в глубину – это обход графа по возможным путям, когда нужно сначала полностью исследовать одну ветку и только потом переходить к другим веткам (если они останутся нерассмотренными).

Поиск в ширину – это обход графа по возможным путям, когда после посещения вершины, посещаются все соседние с ней вершины.

Простой граф – это граф, в котором нет ни петель, ни кратных ребер.

Путь – это открытая цепь, у которой все вершины различны.

Ребра (дуги) графа – это множество линий, соединяющих вершины графа.

Связный граф – это граф, у которого для любой пары вершин существует соединяющий их путь.

Смежные вершины – это вершины, соединенные общим ребром.

Смешанный граф – это граф, содержащий как ориентированные, так и неориентированные ребра.

Список ребер – это множество, образованное парами смежных вершин

Тупик – это вершина графа, для которой все смежные с ней вершины уже посещены

Цепь – это маршрут в графе, у которого все ребра различны.

Цикл – это замкнутая цепь, у которой различны все ее вершины, за исключением концевых.