dfs-bfs.md

DFS & BFS

Примем следующие общие обозначения:

• n -- число вершин в графе
• m -- число ребер в графе
• g -- представление графа в виде списка смежности (в списке под номером v лежит список номеров вершин, смежных с v)
• a -- представление графа в виде матрицы смежности (на пересечении строки v и столбца u стоит True, если вершины v и u смежны)

DFS

Обход всех вершин, при котором в стеке лежит путь от стартовой вершины к текущей вершине.

Пусть visited -- массив меток посещения вершин, изначально заполненный False.

Рекурсивный DFS на списке смежности:

def dfs(v):
    visited[v] = True
    for u in g[v]:
        if not visited[u]:
            dfs(u)

Необходимо знать вершину, с которой начинать обход.

dfs(start)

Выходит, что все вершины, для которых метка в visited равна True, достижимы из вершины start.

Время работы: O(n + m)

DFS на матрице смежности будет немного отличаться:

def dfs(v):
    visited[v] = True

    for u in range(n):                 # <-- вот
        if a[v][u] and not visited[u]: # <-- здесь!

            dfs(u)

Время работы: O(n^2)

Нерекурсивный DFS (понять, простить, забыть):

def dfs(start):
    s = stack()
    s.push(start)
    while not s.empty():
        v = s.top()
        visited[v] = True
        is_top = True
        while last[v] < len(g[v]):
            u = g[v][last[v]]
            last[v] += 1
            if not visited[u]:
                s.push(u)
                is_top = False
                break
        if is_top:
            s.pop()

Здесь last -- массив индексов последних обработанных смежных вершин, изначально заполненный 0.

А если компонент связности много, но хочется обойти все?

for v in range(n):
    if not visited[v]:
        dfs(v)

Немного модифицируем -- и уже можем посчитать число компонент.

components = 0

for v in range(n):
    if not visited[v]:
        dfs(v)
        components += 1 # <-- здесь!

Добавим одну строчку в dfs -- и уже знаем, каким компонентам принадлежат вершины. Для этого заведем массив component, содержащий имена компонент связности, которым принадлежат вершины.

def dfs(v):
    visited[v] = True
    
    component[v] = components # <-- здесь!
    
    for u in g[v]:
        if not visited[u]:
            dfs(u)

А если хотим знать порядковый номер вершины в обходе? Пусть он хранится в массиве ord.

next_idx = 0

def dfs(v):
    visited[v] = True
    
    ord[v] = next_idx # <-- опять
    next_idx += 1     # <-- здесь!
    
    for u in g[v]:
        if not visited[u]:
            dfs(u)

Вопрос: а если мы хотим знать, из какой вершины мы пришли в текущую вершину? Ответ:

def dfs(v):
    visited[v] = True
    for u in g[v]:
        if not visited[u]:

            pred[u] = v # <-- здесь!

            dfs(u)


for v in range(n):
    if not visited[v]:

        pred[v] = None # <-- и здесь!

        dfs(v)

Вместо None можно использовать -1 или v, если мы точно знаем, что нет петель. Зная метки pred, можно восстановить пути из стартовой вершины во все остальные вершины.

Топологическая сортировка

Рассмотрим проблему топологической сортировки вершин ориентированного графа. Будем говорить, что вершина v зависит от вершины u, если есть дуга (v, u). Порядок вершин после такой сортировки гарантирует, что все зависимые вершины будут иметь больший индекс, чем вершины, от которых они зависят. Что же делает DFS? Он обходит все достижимые вершины из фиксированной вершины v перед тем, как выйти из dfs(v). Это значит, что вершины, от которых зависит v, будут уже обработаны к моменту выхода из dfs(v), и порядок выхода из функции dfs определяет порядок топологической сортировки.

Заведем список topsorted, в который будем заносить вершины в порядке топологической сортировки.

topsorted = []

def dfs(v):
    visited[v] = True
    for u in g[v]:
        if not visited[u]:
            dfs(u)

    topsorted.append(v) # <-- здесь

Однако порядок топологической сортировки неопределен, если в орграфе есть ориентированные циклы. Поэтому необходимо добавить проверку на их наличие. Для этого заведем массив in_stack, изначально заполненный False, который будет хранить True, если вершина находится в стеке.

topsorted = []

def dfs(v):
    visited[v] = True

    in_stack[v] = True # <-- здесь!

    for u in g[v]:

        if in_stack[u]: # <-- и еще
            panic!      # <-- здесь!

        if not visited[u]:
            dfs(u)
    
    topsorted.append(v)

    in_stack[v] = False # <-- и вот здесь!

Обработка исключительной ситуации может различаться в зависимости от реализации.

Список topsorted можно перевернуть, чтобы дуги были ориентированы слева направо.

Сильно связные компоненты

Рассмотрим конденсацию графа g, то есть граф, в котором все сильно связные компоненты свернуты в одну вершину. Очевидно, что этот граф ацикличен, а значит, его можно отсортировать. Если запишем вершины в порядке выхода из функции dfs, то самая последняя вершина в этом списке будет принадлежать "корню" конденсированного графа. Воспользуемся фактом, что если транспонировать сильно связную компоненту, то мы все равно получим сильно связную компоненту. Таким образом, если транспонировать граф и запустить DFS из последней вершины, то мы посетим только вершины внутри одной сильносвязной компоненты. Соответственно, следующей непосещенной вершиной будет "корень" конденсированного графа без уже посещенной компоненты, и так далее. Таким образом, задача решается двумя обходами DFS.

Пусть rg -- транспонированный граф g, то есть граф, в котором все ребра развернуты в обратную сторону.

ordered = []
components = 0

def dfs1(v):
    visited[v] = True
    for u in g[v]:
        if not visited[u]:
            dfs1(u)

    ordered.append(v) # <-- здесь!

def dfs2(v):
    visited[v] = True

    component[v] = components # <-- и еще
    for u in rg[v]:           # <-- здесь!

        if not visited[u]:
            dfs2(u)

def strongly_connected_components():
    for v in range(n):
        if not visited[v]:
            dfs1(v)

    for v in range(n):
        visited[v] = False

    for v in reversed(ordered):
        if not visited[v]:
            dfs2(v)
            components += 1

Двудольность графа

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

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

is_bipartite = True

def dfs(v): 
    visited[v] = True

    for u in g[v]:

        if visited[u] and part[v] == part[u]: # <-- вот
            is_bipartite = False               # <-- здесь!
        
        if not visited[u]:

            part[u] = not part[v] # <-- и вот здесь!
            
            dfs(u)

for v in range(n):
    if not visited[v]:

        part[v] = True # <-- и еще здесь!
        
        dfs(v)

BFS

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

На списке смежности:

def bfs(start):
    q = queue()
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()
        
        for u in g[v]:
            if not visited[u]:
                visited[u] = True
                q.enqueue(u)

Время работы: O(n + m)

На матрице смежности отличия те же, что и у DFS:

def bfs(start):
    q = queue()
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()
        
        for u in range(n):                 # <-- вот
            if a[v][u] and not visited[u]: # <-- здесь!
                
                visited[u] = True
                q.enqueue(u)

Время работы: O(n^2)

Если нужно посетить все компоненты связности, то поступаем аналогично с DFS:

for v in range(n):
    if not visited[v]:
        bfs(v)

Проставим метки вершинам в порядке их посещения:

next_idx = 0

def bfs(start):
    q = queue()
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()

        ord[v] = next_idx # <-- вот
        next_idx += 1     # <-- здесь!
        
        for u in g[v]:
            if not visited[u]:
                visited[u] = True
                q.enqueue(u)

Так как мы заходим в if для каждой вершины лишь один раз, то метку с порядком посещения можно выставить и внутри него. Однако в этом случае необходимо выставлять метку для стартовой вершины отдельно.

next_idx = 0

def bfs(start):
    q = queue()
    
    ord[start] = next_idx # <-- вот
    next_idx += 1         # <-- здесь!
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()
        
        for u in g[v]:
            if not visited[u]:
                visited[u] = True
                
                ord[u] = next_idx # <-- и вот
                next_idx += 1     # <-- здесь!
                
                q.enqueue(u)

Если хотим найти растояние в ребрах до всех вершин:

def bfs(start):
    q = queue()

    dist[start] = 0 # <-- здесь!
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()
        
        for u in g[v]:
            if not visited[u]:
                visited[u] = True

                dist[u] = dist[v] + 1 # <-- и здесь!

                q.enqueue(u)

где dist -- массив, хранящий расстояния от стартовой вершины, изначально заполненный -1, None или INF.

Если мы хотим найти кратчайшие по числу рёбер пути до всех вершин от стартовой:

def bfs(start):
    q = queue()

    pred[start] = None # <-- здесь!
    
    visited[start] = True
    q.enqueue(start)

    while not q.empty():
        v = q.dequeue()
        
        for u in g[v]:
            if not visited[u]:
                visited[u] = True

                pred[u] = v # <-- и здесь!

                q.enqueue(u)

Теперь пути можно восстановить по массиву pred.

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