DFS.

[Пaвeл]

Какая сложность алгоритма, который проверяет связность графа.
Вот мой алгоритм:

Procedure DFS(v:longint);
var i:longint;
begin
b[v]:=1;
for i:=1 to n do
if a[v,i]=1 then if b[i]=0 then DFS(i);
end;

...

DFS(1);
for i:=1 to n do
if b[i]=1 then begin
writeln('Граф не связан');
readln;
halt(0);
end;
writeln('Граф связан');

...

B[i]=1, если из вершины 1 можно добраться до вершины i

А какая будет сложность, если вместо матрицы смежности использовать список ребер?

[L_M]

Если я не ошибаюсь, то кольчество вершин + количество ребер(он должен пройти по всем вершинам и для каждой проверять ребра на смежность - строка матрицы). Если использовать список ребер, то по идее должна зависеть от насыщенности графа( ну сколько там ребер ), т.к. по метрице идет поиск по строке - не более n, а в списке ребер надо искать по всем ребрам(если их меньше n, то быстрее, если больше, то медленнее), хотя если отсортировать можно ускорить. Но тогда проще использовать списки смежных вершин, то есть массив в котором для каждой вершины написаны вершины, с которыми она смежна(лучше это на списках).
PS мне кажется лучше в DFS не помечать пройденные вершины, а удалять ребра и если граф не ориентирован, то искать только в части таблицы(т.к она сиимметрична)
for i:=v to n do
if a[v,i]=1 then begin
a[v,i]=0;
DFS(i);
end;

[Пaвeл]

Большое спасибо!