def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1]
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Топологическая сортировка:", result)
Это алгоритм Тарьяна на Python с одного сайта, у этого алгоритма мне непонятно одно(в объяснениях Википедии тоже), это же O(n^2) , так как здесь вызываются два цикла?
Wataru, Зачем в алгоритме сортировки Кана вначале требуется степень, вроде и без неё всё работает? Есть ли возможность сортировать не узлы, а рёбра сразу? Можно ли таким образом обнаружить, что этот граф содержит изолированные узлы, которые могут быть соединены между собой?
Вопрос как вообще обозначать графы? Я делал это через один список узлов с числовыми значениями, два для рёбер, в одном есть входные, в другом соответсвенно по индексу выходные.
Т.е.:
[4, 7, 8, 1, 0] - список узлов, первые две корневые вершины графа(ну может быть и больше или меньше), третий выход
[0, 3, 4]-рёбра(список индексов узлов). Вход
[4, 2, 3]-рёбра(список индексов узлов). Выход.
Просто по-моему оказалось, что их обозначают по другому
Это алгоритм Тарьяна на Python с одного сайта, у этого алгоритма мне непонятно одно(в объяснениях Википедии тоже), это же O(n^2) , так как здесь вызываются два цикла?