Занятие 6

Занятие 6: Применение обхода в глубину. Алгоритм Флойда-Уоршелла

Ориентированные графы без циклов (Directed Acyclic Graphs, DAG)

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

Существует два алгоритма топологической сортировки — алгоритм Кана и алгоритм Тарьяна.

Алгоритм Кана

Это не эффективный алгоритм! Его асимптотика $O(N^2)$ от количества вершин, и его не следует применять на практике.

  1. Среди всех вершин ищем такую, у которой входящая степень вершины равна нулю (т.е. нет входящих рёбер). Если такой вершины нет, то в орграфе есть цикл, и топологическую сортировку выполнить невозможно.
  2. Даём ей очередной номер, а затем удаляем её из графа.
  3. Повторяем пункты 1-2 до тех пор, пока все вершины не окажутся пронумерованными.

Алгоритм Тарьяна

Эффективный алгоритм с асимптотикой $O(N)$ от количества вершин.

  1. Берём первую попавшуюся вершину. Делаем обход графа в глубину от неё. Нумеруем каждую пройденную вершину на выходе из обхода (при "покраске" в "чёрный цвет"). Множество "покрашенных" обходом вершин не забываем — оно ещё пригодится для следующих обходов.
  2. Пока множество "покрашенных" вершин не пусто, повторяем обход из пункта 1 от любой из не пройденных ранее вершин. При этом в обходе "покрашенные" ранее вершины уже не участвуют.
  3. После нумерации всех вершин нужно поменять их нумерацию на противоположную. Впрочем, можно изначально нумеровать их от большего номера к меньшему.

Реализация алгоритма Тарьяна топологической сортировки

In [5]:
def input_graph():
    n, m = map(int, input().split())
    G = {k:set() for k in range(n)}
    for i in range(m):
        a, b = map(int, input().split())
        G[a].add(b)
    return G

G = input_graph()

5 7
0 1
0 2
2 1
4 3
2 3
4 2
4 0
In [6]:
print(G)

{0: {1, 2}, 1: set(), 2: {1, 3}, 3: set(), 4: {0, 2, 3}}
In [7]:
# Tarjan algorithm
def dfs(v, G, black, gray, order):
    assert v not in black, "strange situation. Should not happen."
    if v in gray: # loop in the graph! Can't do topological sort
        print("NO")
        exit(-1)
    else:
        gray.add(v)
        for u in G[v]:
            if u not in black:
                dfs(u, G, black, gray, order)
        gray.remove(v)
        black.add(v)
        order.append(v)

order = []
white = set(range(len(G)))
black = set()
while white:
    v = white.pop()
    dfs(v, G, black, set(), order)
    white -= black
print(' '.join(map(str, order[::-1])))

4 0 2 3 1

Реализация алгоритма Косарайю выделения сильно связных компонент орграфа

При считывании списка рёбер сохраним не только прямой граф, но и транспонированный (с обращённым направлением рёбер):

In [1]:
def input_graph():
    n, m = map(int, input().split())
    G = {k:set() for k in range(n)}
    G_transposed = {k:set() for k in range(n)}
    for i in range(m):
        a, b = map(int, input().split())
        G[a].add(b)
        G_transposed[b].add(a)
    return G, G_transposed

G, G_transposed = input_graph()

5 7
0 1
0 2
2 1
4 3
2 3
4 2
4 0

Теперь делаем серию обходов в глубину для транспонированного графа, сохраняя порядок выхода из вершин в списке order:

In [3]:
def dfs(v, G, gray, order):
    gray.add(v)
    for u in G[v]:
        if u not in gray:
            dfs(u, G, gray, order)
    order.append(v)

order = []
white = set(G.keys())
used = set()
while white:
    v = white.pop()
    dfs(v, G_transposed, used, order)
    white -= used
print(' '.join(map(str, order[::-1])))

3 1 2 0 4

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

In [4]:
def dfs2(v, G, gray, component):
    gray.add(v)
    component.add(v)
    for u in G[v]:
        if u not in gray:
            dfs2(u, G, gray, component)

# second part
black = set()
while len(black) != len(G):
    v = order.pop()  # берём вершину с конца очереди (из стека)
    while v in black:  # если вершина уже пройдена предыдущим обходом, то пропускаем её
        v = order.pop()  # берём вершину с конца очереди (из стека)
    component = set()
    dfs2(v, G, black, component)
    print("component:", component)

component: {3}
component: {1}
component: {2}
component: {0}
component: {4}

Алгоритм Флойда-Уоршелла

Это алгоритм поиска кратчайших путей во взвешенном графе с положительным или отрицательным весом ребер (но без отрицательных циклов). За одно выполнение алгоритма будут найдены длины (суммарные веса) кратчайших путей между всеми парами вершин. Хотя он не возвращает детали самих путей, можно реконструировать пути с помощью простых модификаций алгоритма.

Описание алгоритма Флойда в Википедии

Ролик с объяснением алгоритма Флойда

Статья в учебнике Фоксфорда про алгоритм Флойда с реализацией на Python

In [ ]: