Przejdź do treści

Sortowanie topologiczne

Opis problemu

Implementacja

 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
def topological_sort(graph: list) -> list:
  in_ranks = [0] * len(graph)
  removed = [False] * len(graph)
  result = []

  for neighbours_list in graph:
    for node in neighbours_list:
        in_ranks[node] += 1

  change = True

  while change and len(result) < len(graph):
    change = False

    for i, neighbours_list in enumerate(graph):
      if removed[i] or in_ranks[i] > 0:
        continue

      change = True
      result.append(i)
      removed[i] = True

      for node in neighbours_list:
          in_ranks[node] -= 1

  return result

graph = [
        [2],
        [0, 2],
        [],
        [1, 0, 4],
        [2, 1],
        [0, 4],
]

result = topological_sort(graph)

if len(result) < len(graph):
  print("Graph has a cycle")
else:
  print(" ".join(map(str, result)))