Поиск в глубину ( DFS ) в графе. Pascal, Delphi.

Поиск в глубину в графе используется в основном для поиска количества компонентов связности, а также для поиска циклов в графе.

Что делает поиск в глубину(DFS)? Он проходит вершины в графе, смежные с изначальной и помечает пройденные. Вот и все.
А теперь код:

Код:


Procedure DFS(v: integer)// v это текущая вершина.
Var i: integer;
Begin
  marked[v] := true;
  For i := 1 to n do
  if (a[v, i] = 1) and (not marked[i]) then dfs(i); //a - это матрица смежности графа(1 - есть ребро, 0 - нет).
End;


Примечание: не забудьте заполнить массив marked(помеченные) False'ами.

Процедура помечает вершину(v), затем проходится по всем вершинам и смотрит, если вершина не помечена и смежна с данной(v), то запускается от нее.

Матрица смежности(a) в процедуру не передается, так как я использовал Делфи. В Паскале не забудьте это сделать.