Статья Автор: Лебедев Дмитрий Алексеевич

Обработка графов

Попробуем "причесать" некоторые алгоритмы под практические задачи.
Вначале введем обозначения, которых будем стараться придерживаться:
  1. Компоненты связанности вершин Adj. 
    Adj[u] - набор вершин, с которыми вершина u соединена
    Adj = словарь <вершина, множество/словарь смежных вершин>
    получаем из входных данных (списка ребер, матрицы смежности)
  2. Множество всех вершин Vertices 
    Vertices[u] - значимые (для данной задачи) характеристики вершины
    Обычно Vertices = словарь <вершина. "значение">
    Vertiсes = dict.fromkeys(Adj, -1) - это "стандартный" способ получения 
    словаря вершин для задач, в которых надо "зачем-то обойти граф"
  3. Множество ребер/путей Edges
    Edges[(u,v)] - содержит значение, характеризующие вершины графа u, v
    (длины ребра или длину пути, весть требуемый путь и т.п.)
    Edges = словарь <пара ребер, значение>
  4. Возможно еще использование
    - множество компонент смежности (сильной связанности)
    - топологической сортироваки и др.
Для практического применения все имена сокращают до заглавной буквы, а сам граф описывают с помощью кортежа, например G(V,E) или G(A. V)
Постораемся придерживаться этого при решении задач.

В примерах, вначале будем описывать используемые объекты,
Затем в программе start - создание/инициализацию этих объёктов
Для стандартных алгоритмов DFS и BFS будем использовать расширенные названия 
типа dfs_color, bfs_dist - чтобы они были разными (в программировании принято использовать
просто dfs и bfs)

Пример 1. bfs
Необходимо определить наличие пути и его длину между вершинами неориентированного графа.
Способ задания может быть как матрицей смежности, так и списком ребер.
Входные данные 
df_001.txt  : 1 строка одно число N - число вершин (размер квадратной матрице)
следущие N строк - строки матрицы
последняя строка - два числа, для которых определяется путь (нумерация вершин начинается с 1)
Решим задание с использованием BFS


В список вершин изначально записали  -1.
Это означало, что вершина не просматривалась.
Из стартовой вершины организовали "очередь" (используя обычный список),
по которой "бежали" добавляя "по ходу" новые вершины.
Поскольку в BFS заход в вершину "гарантирует минимальный путь в ребрах", 
то добавлять можно только новые вершины, а путь удлинять на 1

Пример 1. dfs
Решение той же задачи с помощью DFS
Заносим путь до стартовой вершины и запускаем DFS.
Запускаем для новых или в случае обнаружения более короткого пути.


Пример 2. dfs
Необходимо определить отсутствие/наличие цикла в ориентированном невзвешанном графе.
Способ задания может быть как матрицей смежности, так и списком ребер.
Входные данные 
df_002.txt  : 1 строка одно число N - число вершин (размер квадратной матрице)
следущие N строк - строки матрицы
Выходные данные:
Если циклов нет (граф ациклический), то вывести YES
При наличии цикла вывести NO и одну из вершин цикла (любого)
Для решения задания будем последовательно перебирать вершины разных компонент связности  и  проверять 
каждую на ацикличность.
Решим задание с использованием DFS
Идея решения состоит в том, что при "входе в вершину" будем устанавливать флажок в состояние 1, а при выходе переводить его в 2. Если по ходу встретим вершину с флажком 1, то это означает повторный вход и обозначает наличие цикла с этой вершиной. Выйдем из dfs  без закрытия (у этой вершины будет состояние 1)
 


Пример 2. bfs
Проверку наличия цикла с помощью BFS на ориентированных графах, обычно не делают, но попробуем это сделать в учебных целях.
 



Печать