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

DFS: Способы реализации

Поиск в глубину (depth-rst search – DFS) – прямолинейный способ обхода графа. Алгоритм начинает работу в начальной вершине и перебирает все вершины, достижимые из нее по ребрам графа. Поиск в глубину всегда следует по одному пути, пока на нем еще имеются вершины. После этого он возвращается назад и начинает исследовать другие части графа. Алгоритм запоминает посещенные вершины, так что каждая обрабатывается только один раз.

С помощью алгоритма DFS мы можем проверить многие свойства графа.
Проверка связности. Граф называется связным, если между любыми двумя вершинами существует путь. Следовательно, для проверки связности мы можем начать с произвольной вершины (для неориентированного графа) и выяснить, все ли вершины достижимы из нее.
Можно также найти все компоненты графа: для этого нужно перебрать все вершины и начинать новый поиск, если текущая вершина не принадлежит ни одной из уже найденных компонент связности.
Обнаружение циклов. Граф содержит цикл, если в процессе обхода мы встречаем такую вершину, что одна из соседних с ней (кроме той, что предшествует ей на текущем пути) уже посещалась.
Проверка на двудольность. Граф называется двудольным, если его вершины можно раскрасить двумя цветами, так что никакие две соседние вершины не будут окрашены одним цветом. Удивительно, как просто можно проверить граф на двудольность с помощью алгоритмов обхода.
Идея в том, чтобы выбрать два цвета X и Y, окрасить начальную вершину цветом X, всех ее соседей – цветом Y, всех их соседей – цветом X и т. д.
Если в какой-то момент мы обнаруживаем, что две соседние вершины окрашены одним цветом, значит, граф не является двудольным.
В противном случае граф двудольный, и мы нашли доказывающую это раскраску.
И многие другие задачи ...

Для применении алгоритма DFS удобнее всего использовать представление графа в виде списков смежности.

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

словарь или список adj (adj[x]= список/словарь, элементы которого есть описание ребер в смежные вершины :

вершина - для невзвешенного графа
(вершина, вес) - для взвешенного граф

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

for u in adj[s] :
# обработать вершину u

Реализация DFS. Поиск в глубину удобно реализовать рекурсивно. Приведем реализацию DFS для следующих условий:
граф представлен списком смежности adj;
в списке вершин visited отмечается "посещение" данной вершины алгоритмом. В начальный момент все элементы этого массива имеют значение False, но когда алгоритм заходит в вершину u, в элемент visited[u] записывается значение True
Функцию можно реализовать следующим образом:

Задача
В неориентированном графе найти компоненту связности заданной вершины.
В графе могут быть петли и кратные ребра.
Входные данные: В первой строке записаны сначала два числа N, M и start, задающие соответственно количество вершин, количество ребер и стартовую вершину ( вершины нумеруются от 0 до N-1), а затем перечисляются ребра. Каждое ребро задается двумя номерами вершин, которые оно соединяет.
Выходные данные: Состав компоненты связности (в произвольном порядке)
Ниже приведено возможное решение (Программа DFS-01) этой задачи. Проверьте это решение на следующием наборе данных.
8 7 1
1 2
2 3
3 4
4 1
5 6
6 7
0 7

''' Программа DFS-01 '''
def dfs(v,adj,visited): # обход графа в глубину
  # v - вершина входа, adj - список смежности
  # visited - список посещения
    if visited[v] : return # проверка на повторный заход
    visited[v]=True # отмечаем вход
    print(v,end=' ') # вывод входа в вершину на печать 
    for u in adj [v] : # обход списка смежности входной вершины
        dfs(u, adj,visited) # запуск DFS от вершины назначения
    print(v,end=' ') # вывод выхода из вершины на печать 
     
N,M,start=map(int,input().split()) # N - кол-во вершин, M - кол-во ребер, стартовая 
adj=[[] for i in range(N)] # построение списка смежности неориентированного графа
for i in range(M): # чтение ребер
  a,b=map(int,input().split()) # ребро 
  adj[a].append(b) # фиксация в списке смежности вершины a
  adj[b].append(a) # фиксация в списке смежности вершины b
visited=[False]*N # создание списка посещений
dfs(start, adj,visited) # запуск DSF из стартовой вершины

Пример показывает, что при реализации алгоритма DFS, каждая вершина посещается ровно один раз.
В программе DFS-01 вершина выводилась на печать при "входе" в неё.
Добавим в подпрограмму dfs еще один оператор ( вывод вершины при "выходе").
Запустите программу DFS-02 и сравните результаты с выводом DFS-01

''' Программа DFS-02 '''
def dfs(v,adj,visited): # обход графа в глубину
  # v - вершина входа, adj - список смежности
  # visited - список посещения
    if visited[v] : return # проверка на повторный заход
    visited[v]=True # отмечаем вход
    print(v,end=' ') # вывод входа в вершину на печать 
    for u in adj [v] : # обход списка смежности входной вершины
        dfs(u, adj,visited) # запуск DFS от вершины назначения
    print(v,end=' ') # вывод выхода из вершины на печать 
     
N,M,start=map(int,input().split()) # N - кол-во вершин, M - кол-во ребер, стартовая 
adj=[[] for i in range(N)] # построение списка смежности неориентированного графа
for i in range(M): # чтение ребер
  a,b=map(int,input().split()) # ребро 
  adj[a].append(b) # фиксация в списке смежности вершины a
  adj[b].append(a) # фиксация в списке смежности вершины b
visited=[False]*N # создание списка посещений
dfs(start, adj,visited) # запуск DSF из стартовой вершины

Примеры программ DFS-01, DFS-02 наталкивают на использование "счётчика времени" при обходе графа с помощью DFS.
Если изменить тип visited на словарь, то при посещении вершины её можно добавлять в словарь, а в качестве значения хранить время захода и/или время выхода. Использование времени "входа/выхода" один из основных приёмов при решении задач с использованием алгоритма DFS
Это можно реализовать примерно так:

''' Программа DFS-03 '''
def dfs(v,adj,visited,t=0): # обход графа в глубину
  # v - вершина входа, adj - список смежности
  # visited - словарь посещения, t - таймер обхода
    if v in visited : return # проверка на повторный заход
    visited[v]=t # отмечаем вход
    t+=1 # увеличили такт времени
    for u in adj [v] : # обход списка смежности входной вершины
        dfs(u, adj,visited,t) # запуск DFS от вершины назначения
    visited[v]=(visited[v],t) # добавляем выход 
    t+=1 # увеличили такт времени
    return t
     
N,M,start=map(int,input().split()) # N - кол-во вершин, M - кол-во ребер, стартовая 
adj=[[] for i in range(N)] # построение списка смежности неориентированного графа
for i in range(M): # чтение ребер
  a,b=map(int,input().split()) # ребро 
  adj[a].append(b) # фиксация в списке смежности вершины a
  adj[b].append(a) # фиксация в списке смежности вершины b
visited=dict() # создание словаря посещений
t=0
for v in range(N): # запуск DSF для всех вершин графа
  t=dfs(v, adj,visited,t) # запуск DSF из стартовой вершины
print(*sorted(visited.items()), sep='\n') # печать словаря посещений

Чтобы оставить комментарий нужна авторизация

Печать