Поиск компонент сильной связности в орграфе (реализация на Python)

Без рубрики   6 Июнь 2016  Автор статьи: Александр Гавриков 

Задан ориентированный граф, состоящий из N вершин и M дуг. Исходный орграф задается списком дуг. Требуется выделить в орграфе компоненты сильной связности.

Для решения данной задачи исходный орграф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Транспонированный орграф adjT также представляется в памяти ЭВМ списком смежности. Список used служит для отметки о том, стала вершина v посещенной в процессе обходов орграфа или еще нет. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка topSort. Для принадлежности вершины к той или иной компоненте связности используется массив component.

1
2
3
4
5
6
adj = [[] for i in range(n)] #список смежности орграфа
adjT = [[] for i in range(n)] #список смежности транспонированного орграфа
used = [False for i in range(n)] #массив для хранения информации о пройденных и не пройденных вершинах
color = [int(0) for i in range(n)] #массив для хранения цветов вершин
topSort = [] #топологически упорядоченная перестановка вершин графа
component = [int(0) for i in range(n)] #массив для обозначения компонент сильной связности орграфа

В качестве списка смежности для представления графа на языке Python 3.0 удобно использовать список списков.
В приведенной ниже реализации данные считываются и выводятся в консоль.

Входные данные

В первой строке входного файла задано два целых числа: N (1 \le N \le 10^5) – количество вершин в орграфе и M (1 \le M \le 10^6) – количество дуг орграфа соответственно. Каждая из следующих M строк содержит описание дуги орграфа – два целых числа из диапазона от 1 до N, номер начала и конца дуги соответственно.

Выходные данные

На первой строке выходного файла выводится число L — количество компонент сильной связности заданного орграфа. На следующей строке выводится N чисел из диапазона от 1 до L — номера компонент сильной связности, которым принадлежат соответствующие вершины. Компоненты сильной связности нумеруются от 1 до L в топологическом порядке в конденсации заданного орграфа.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
'''
@author: agavrikov
'''

n, m = map(int, input().split()) #количество вершин и ребер в графе
adj = [[] for i in range(n)] #список смежности орграфа
adjT = [[] for i in range(n)] #список смежности транспонированного орграфа
used = [False for i in range(n)] #массив для хранения информации о пройденных и не пройденных вершинах
color = [int(0) for i in range(n)] #массив для хранения цветов вершин
topSort = [] #топологически упорядоченная перестановка вершин графа
component = [int(0) for i in range(n)] #массив для обозначения компонент сильной связности орграфа

#считываем граф, заданный списком ребер
for i in range(m):
    v, w = map(int, input().split())
    v -= 1
    w -= 1
    adj[v].append(w)
    adjT[w].append(v)

def dfs(v) : #процедура обхода в глубину
    #если вершина является пройденной, то не производим из нее вызов процедуры
    if used[v]:
        return
    used[v] = True #помечаем вершину как пройденную
    #запускаем обход из всех вершин, смежных с вершиной v
    for w in adj[v]:
        dfs(w) #вызов обхода в глубину от вершины w, смежной с вершиной v
    #добавляем посещенную вершину в топологический порядок
    topSort.append(v)
     
def ccs(v, componentID):
    #если вершина является пройденной, то не производим из нее вызов процедуры
    if used[v]:
        return
    used[v] = True #помечаем вершину как пройденную
    component[v] = componentID
    #запускаем процедуру, которая топологически сортирует вершины графа
    for w in adjT[v]:
        ccs(w, componentID) #вызов обхода в глубину от вершины w, смежной с вершиной v в транспонированном графе

def run():
    for v in range(n):
        dfs(v)
    for i in range(n):
        used[i] = False    
    componentID = 0
    for v in reversed(topSort):
        if not used[v]:
            ccs(v, componentID)
            componentID = componentID + 1
    print(componentID) #выводим количество компонент сильной связности
    for v in component:
        print(v + 1, end=' ')
    print(' ')    
   
run()

 

Пример

Рассмотрим работу алгоритма на графе G, изображенном на рисунке.

орграф

В орграфе G существует четыре компоненты сильной связности.

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

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

конденсация

Входные данные
12 19
1 2
2 3
3 1
3 12
4 2
4 3
4 5
5 6
6 4
7 5
7 8
7 9
8 6
8 7
8 12
9 10
10 11
11 12
12 9
Выходные данные
4
3 3 3 2 2 2 1 1 4 4 4 4

 

Научиться программировать

  • на Delphi

  • на Java

  • на C++