Презентация на тему Алгоритмы на графах. Определение наличия циклов в графе

ориентированном ациклическом графе с n вершинами?
Может ли быть так,

то топологическая сортировка невозможна.
Если граф ациклический, то можно выполнить

Как с помощью топологической сортировки определить наличие циклов в графе?

Pascal
Cycles := False;
for i := 1 to n do
for j := 1 to n do
if A[i, j] and
(order[j] > order[i]) then
Cycles := True;

C
Cycles = FALSE;
for(i = 0; i < n; i++)
for(j = 0; j < n; j++)
if(A[i, j] &&
(order[j] > order[i]))
Cycles = TRUE;

из текущей вершины есть путь в серую вершину, то

Если в графе есть цикл, то почему DFS обязательно его найдёт?

покидаем первую вершину в нём.
Возвращаться будем из вершины X

При заходе в вершину помещаем её в стек, при

Pascal
sp := 0;

Push(v):
Inc(sp);
stack[sp] := v;

Pop:
Dec(sp);

C
sp = 0;

Push(v):
stack[++sp - 1] = v;

Pop:
sp--;

n do
color[i] := WHITE;
rm := False; found :=