Своими словами. Берем первую вершину, смотрим, нет ли у нее инцидентных ребер (прямых потомков), если есть помечаем, повторяем процедуру для найденной вершины, и так до конца глубины. Возвращаемся, идем к соседней вершине, и так далее.
interface
|
1 2 |
var IsVisitedGlobal:array [1..N] of boolean; |
init visited array
|
1 |
for i := 0 to High(IsVisitedGlobal) do IsVisitedGlobal[i]:=false; |
dfs
|
1 2 3 4 5 6 7 8 9 |
procedure TMain.DFS(AAdjencyMatrix: TAdjencyMatrix; AsizeOfAdjMatrix, AStartNode: integer ); var i:Integer; begin IsVisitedGlobal[AStartNode]:=true; // do somesting else here for i := 0 to AsizeOfAdjMatrix do if (AAdjencyMatrix[AStartNode,i]<>0) and not IsVisitedGlobal[i] then DFS(AAdjencyMatrix,AsizeOfAdjMatrix,i); end; |
Теперь, если наш граф не дерево с единственным корнем, обходим по всем узлам
|
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; |