Проверка правильности топологической сортировки

Question

Учитывая следующий ориентированный граф:

Я определил топологическую сортировку как 0, 1, 2, 3, 7, 6, 5, 4 со значениями для каждого узла:

d[0] = 1
f[0] = 16

d[1] = 2
f[1] = 15

d[2] = 3
f[2] = 14

d[3] = 4
f[3] = 13

d[4] = 7
f[4] = 8

d[5] = 6
f[5] = 9

d[6] = 5
f[6] = 10

d[7] = 11
f[7] = 12

Где d - время открытия, а f - время окончания.

Как проверить, действительна ли топологическая сортировка или нет?

Answer 1

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

Топологический порядок узлов = порядок (метка) узлов / вершин, такой, что для каждого ребра (u, v) в G, u появляется раньше, чем v в порядке.

Есть два способа, которыми вы могли бы подойти к этому вопросу: с краевой перспективы вершинной перспективы. Я описываю наивную (то есть с некоторой дополнительной пространственной сложностью и сообразительностью, которую вы могли бы улучшить) реализацию обоих ниже.

Подход к краю

Итерация по ребрам в G. Для каждого ребра извлекаем индекс каждой из его вершин в порядке. Сравнил показатели. Если вершина происхождения не ранее, чем вершина назначения, верните false. Если вы перебираете все ребра без возврата false, верните true.

Сложность: O (E * V)

Вершинный подход

Итерация по вершинам в вашем порядке. Для каждой вершины извлеките ее список исходящих ребер. Если любое из этих ребер заканчивается в вершине, которая предшествует текущей вершине в порядке, вернуть false. Если вы перебираете все вершины без возврата false, верните true.

Сложность: O (V ^ 2 * E)

Answer 2

С python и networkx , вы можете проверить это следующим образом:

import networkx as nx

G = nx.DiGraph()
G.add_edges_from([(0, 2), (1, 2), (2, 3)])
all_topological_sorts = list(nx.algorithms.dag.all_topological_sorts(G))
print([0, 1, 2, 3] in all_topological_sorts) # True
print([2, 3, 1, 0] in all_topological_sorts) # False

Однако обратите внимание, что для того, чтобы иметь топологическое упорядочение, граф должен быть направленным ациклическим графом (DAG). Если G не направлено, NetworkXNotImplemented будет возбуждено. Если G не является ациклическим (как в вашем случае), NetworkXUnfeasible будет повышен.

См. Документацию здесь .