На входе бесконтурный орграф (если есть контуры то привет тебе товарищ, не сработает в чистом виде этот алгоритм).
На выходе нужно получить упорядоченный список вершин графа.
Для простоты зададим граф матрицей смежности…
Берем за основу DFS и при каждом проходе добавляем пройденную вершину в наш список. Полученная последовательность и будет результатом сортировки.
Примерный код….
1 2 3 4 5 6 7 8 |
var IsVisitedGlobal:array [1..N] of boolean; NodesOrder:array [1..N] of integer; DirectParent:array [1..N] of integer; lastIndexGlobal:integer; lastIndexGlobal2:integer; |
Процедура рандомного заполнения массива
1 2 3 4 5 6 7 8 9 10 |
procedure TMain.randomInitAdjMatrix( var AAdjencyMatrix:TAdjencyMatrix; AsizeOfAdjMatrix:integer ); // to init random values of AdjMatrix var i,j:integer; begin SetLength(AAdjencyMatrix,AsizeOfAdjMatrix,AsizeOfAdjMatrix); for i := 0 to High(AsizeOfAdjMatrix) do begin for j := 0 to High(AsizeOfAdjMatrix) do begin AAdjencyMatrix[i,j]:=Random(1); end; end; end; |
Инициализация
1 2 3 4 5 6 7 8 9 10 11 12 13 |
constructor TMain.Create(AOwner: TComponent); var i: Integer; begin inherited; for i := 0 to High(Graph) do Graph[i]:=nil; for i := 0 to High(IsVisitedGlobal) do IsVisitedGlobal[i]:=false; lastIndexGlobal:=0; lastIndexGlobal2:=0; randomInitAdjMatrix(AAdjencyMatrix, N); end; |
Рекурсивная процедура обхода в глубину для 1 узла
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
procedure TMain.DFS(AAdjencyMatrix: TAdjencyMatrix; AsizeOfAdjMatrix, AStartNode: integer ); var i:Integer; begin IsVisitedGlobal[AStartNode]:=true; // do something else here NodesOrder[lastIndexGlobal]:=AStartNode; // what is order in topological sort? Inc(lastIndexGlobal); // no parent for AStartNode for i := 0 to AsizeOfAdjMatrix do if (AAdjencyMatrix[AStartNode,i]<>0) and not IsVisitedGlobal[i] then begin DFS(AAdjencyMatrix,AsizeOfAdjMatrix,i); DirectParent[lastIndexGlobal2]:=AStartNode; // who is parent? Inc(lastIndexGlobal2); end; end; |
Полный проход методом DFS для всех узлов
1 2 3 4 5 |
procedure TMain.DFSFull(AAdjencyMatrix: TAdjencyMatrix; AsizeOfAdjMatrix ); var i:integer; begin for i := 0 to AsizeOfAdjMatrix-1 do DFS(AAdjencyMatrix, AsizeOfAdjMatrix,i); end; |