Как применить топологическую сортировку?

Question

[Nem0_o]

Есть алгоритм, реализация с помощью обхода в глубину: rain.ifmo.ru/cat/view.php/vis...2007/algorithm
Код C++

boolean topological_sort(){
       boolean Cycle;
       for(int i = 1;i <= N;i ++){
           Cycle = dfs(i);
           if(Cycle)return false;
       }
       for(int i = 1;i <= n;i ++){
           Numbers[Stack.pop()] = i;
       }
      return true;
  }
  boolean dfs(int v){
      if(Color[v] == 1)return true;
      if(Color[v] == 2)return false;
      Color[v] = 1;
      for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }
      Stack.push(v);
      Color[v] = 2;
      return false;
}

Процедура возвращает true, если граф был топологически отсортирован, иначе возвращается false.

Color — массив, в котором хранятся цвета вершин (0 — белый, 1 — серый, 2 — черный).
N — количество вершин.
Edges — массив списков смежных вершин.
Numbers — массив, в котором сохраняются новые номера вершин.
Stack — стек, в котором складываются вершины после их обработки.
Cycle — принимает значение true, если в графе найден цикл.

Описание:
3—6. Вызывается обход в глубину от всех вершин. Заканчиваем работу алгоритма, если обнаружен цикл.
7—9. Заносим в массив новые номера вершин.
13—14. Если вершина серая, то мы обнаружили цикл. Заканчиваем поиск в глубину.
14. Если вершина черная, то заканчиваем ее обработку.
15. Красим вершину в серый цвет.
16—18. Обрабатываем список смежных с ней вершин.
19. Кладем вершину в стек.
20. Красим вершину в черный цвет.

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

Comments

[Станислав Макаров]

На вскидку, Edges - это ваши списки смежности, т.е. Edges[v] это список вершин, смежных с v. Соответственно, этот массив надо заполнить перед запуском сортировки.
Затем, после обработки, результат можно будет увидеть в map-е Numbers. Структуры Stack и Color по-видимому следует инициализировать дефолтовым конструктором. Теперь укажите, с какого места вам непонятно. Разумеется, как уже сказал brainick, сначала разберитесь с понятиями теории графов, которыми пользуетесь.

Answer 1

[Mercury13]

Нужно переписать под матрицу смежности вот этот участок кода.

for(int i = 0;i < Edges[v].size();i ++){
          if(dfs(Edges[v].get(i)))return true;
      }

Что-то типа этого.

цикл (i : все вершины)
   если матрица_смежности[v, i]
         если dfs(i)
             return true;

Ещё мне не нравятся константы 0, 1 и 2. Объявить бы их как

UNVISITED = 0;
PARTLY_VISITED = 1;
VISITED = 2;

Или WHITE, GRAY и BLACK, если хотите — в учебниках по алгоритмам их красят в три цвета.