Почему мои результаты топологической сортировки нестабильны и нужно ли мне использовать для этого класс? ⇐ Python

[Anonymous]

Я новичок в изучении топологической сортировки на Python.
Я реализовал простую версию алгоритма Кана, используя словарь для представления DAG и функцию для выполнения сортировки.
Код работает без ошибок, но порядок вывода нестабилен.

Когда я запускаю программу несколько раз, порядок шагов меняется, хотя сам график никогда не меняется.
Я ожидал, что шаг, который появляется первым, всегда будет появляться первым, но этого не произошло.
Ожидается ли такое поведение при топологической сортировке или что-то не так с моей реализацией?
Кроме того, я часто вижу в Интернете примеры, в которых используется класс Graph.

Нужно ли мне использовать класс для решения этой проблемы, или мой подход на основе функций подойдет?

Код: Выделить всё

def topological_sort(graph):
topo = []
ready = []
incount = {}

for u in graph:
incount[u] = 0

for u in graph:
for v in graph[u]:
incount[v] += 1

for u in incount:
if incount[u] == 0:
ready.append(u)

while ready:
u = ready.pop()
topo.append(u)

for v in graph[u]:
incount[v] -= 1
if incount[v] == 0:
ready.append(v)

return topo

graph = {
"Wash Rice": ["Soak Rice"],
"Soak Rice": ["Boil Rice"],
"Boil Rice": ["Layer"],
"Layer": ["Dum"],
"Dum": ["Serve"]
}

print(topological_sort(graph))

Почему вывод постоянно меняется и здесь необходим класс?

Подробнее здесь: https://stackoverflow.com/questions/798 ... ss-for-thi