Топологическая сортировка (реализация на Python)

Python   11 Февраль 2016  Автор статьи: Александр Гавриков 

Задан ориентированный граф, состоящий из N вершин и M дуг. Требуется найти топологическую сортировку (topological sort) вершин этого графа, то есть указать такой линейный порядок на его вершинах, что любая дуга ведет от меньшей вершины к большей в смысле этого порядка. В случае, если орграф не является ациклическим и такого порядка не существует, то вывести сообщение об этом.

Для решения данной задачи исходный орграф G удобно представлять в памяти ЭВМ списком смежности adj, храня для каждой вершины графа v список adj[v] смежных с ней вершин. Массив color служит для хранения цветов вершин. Белой вершине v соответствует значение 0 в ячейке color[v], color[v] = 0. Если вершина v в процессе обхода стала серой, то color[v] = 1, если стала черной, то color[v] = 2. Топологически упорядоченная перестановка номеров вершин орграфа хранится при помощи списка topSort.

1
2
3
adj = [[] for i in range(n)] #список смежности
color = [int(0) for i in range(n)] #массив для хранения цветов вершин
topSort = [] #топологически упорядоченная перестановка вершин графа

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

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

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

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

Если орграф не является ациклическим и содержит один или более циклов, то в первой строке выводится слово «Сyclic». Если орграф является ациклическим, то в строке выводится N чисел через пробел — топологическая сортировка вершин орграфа.

 

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
'''
@author: agavrikov
'''


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

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

def topologicalSort(v) : #топологическая сортировка вершин графа
    #если вершина является черной, то не производим из нее вызов процедуры
    if color[v] == 2:
        return True
    #если вершина является серой, то орграф содержит цикл, выходим из процедуры
    if color[v] == 1:
        return False
    color[v] = 1 #помечаем вершину как серую
    #запускаем обход из всех вершин, смежных с вершиной v
    for w in adj[v]:
        #вызов обхода от вершины w, смежной с вершиной v
        if not topologicalSort(w):
            return False
    color[v] = 2 #помечаем вершину как черную
    #добавляем посещенную вершину в топологический порядок
    topSort.append(v)
    return True
     
def run():
    cyclic = False #флаг, показывающий содержит орграф цикл или нет
    #запускаем процедуру, которая топологически сортирует вершины графа
    for v in range(n):
        if not topologicalSort(v):
            cyclic = True
    if not cyclic:
        topSort.reverse()
        #иначе выводим топологически упорядоченную перестановку его вершин
        for v in topSort:
            print(v + 1, end=' ')
    else:
        print('Cyclic')

run()

 

Пример
Входные данные
9 9
1 4
1 5
2 5
4 5
4 7
6 3
7 9
8 7
8 9
Выходные данные
8 6 3 2 1 4 7 9 5

 

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

  • на Delphi

  • на Java

  • на C++