Pseudo Code

Урок 4 из 9 курса Топологическая сортировка — алгоритмы на графах на Coddy.

topologicalSort(n, edges):
   build directed adjacency; compute indeg[v] for all v
   order = []
   repeat n times:
      pick = smallest v with indeg[v] == 0 (none left -> stop)
      mark pick as used (indeg[pick] = -1)
      order.add(pick)
      for nb in adj[pick]:
         indeg[nb] -= 1
   return order

indeg[v] подсчитывает входящие ребра. Только ребра u -> v увеличивают indeg[v].
Сканирование вершин 0..n-1 и выбор первой с полустепенью захода 0 дает наименьший вариант на каждом шаге, поэтому порядок является детерминированным.
Установка indeg[pick] = -1 — это простой способ пометить вершину как уже размещенную.

Попробуйте сами

В этом уроке нет задания по программированию.

Проверьте себя

В этом уроке есть небольшой тест. Начните урок, чтобы ответить на вопросы и сохранить прогресс.

Все уроки раздела Топологическая сортировка — алгоритмы на графах

1Introduction

Introduction Motivation

2The Algorithm

How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)

Time and Space Complexity

3Final Challenges

Final Challenge #1 Final Challenge #2