Например дан граф из 6 вершин
Тогда мы можем расположить вершины в такое порядке: 5 2 7 1 3 6. Почему так? Потому что: 5 --> 2, 2 --> 7, 5 --> 1, 1 --> 3, 1 --> 6, 3 --> 6. Все стрелки --> получились одинаковыми, а значит мы отсортировали граф топологически.
Реализация поиском глубиной
Перебираем все вершины и смотрим, что если она не помеченная (used массив меток), тогда из нее пускаем глубину
for i:=1 to n do if not(used[i]) then dfs(i);
Рассмотрим dfs. Думаю, я не буду все расписывать, ведь всё указано в пунктах выше, разве что некоторые моменты
procedure dfs(v:longint); var i:longint; begin used[v]:=false; //помечаем вершину, типа мы здесь были for i:=1 to n do if (not(used[i])) and (g[v,i]=1) //если мы не были в этой вершине и есть путь из вершины v в нашу then begin parent[i]:=v; //предком для нашей вершины является вершина v, т.е. мы пришли из неё dfs(i); //глубиной идем от нашей вершины end; inc(cnt); //увеличиваем счетчик dag[cnt]:=v; //в массив тоположки кидаем нашу вершину v end;
Ну и сам вывод массива вершин, топологически отсортированного
for i:=cnt downto 1 do write(dag[i],' ');
Сообщение отредактировал Санек: 20 ноября 2012 - 17:25