пошук циклу в орієнтованому графі.

Ще одне застосування DFS - пошук циклу в орієнтованому графі.

Цикл в орієнтованому графі можна виявити при наявності ребра, що веде з поточної вершини в вершину, яка зараз знаходиться в стадії обробки, тобто алгоритм DFS зайшов у таку вершину, але ще не вийшов з неї.

У такому алгоритмі DFS будемо фарбувати вершини в три кольори.

Кольором 0 («білий») будемо позначати ще невідвідані вершини.

Кольором 1 («сірий») будемо позначати вершини в процесі обробки.

Кольором 2 («чорний») будемо позначати вже оброблені вершини.

Вершина фарбується в колір 1 при заході в цю вершину і в колір 2 - при виході.

Цикл в графі існує, якщо алгоритм DFS виявляє ребро, кінець якого пофарбований в колір 1.

процедура DFS (початок: ціле число);

 були: ціле;

почати

  Колір [початок]: = 1;

  для i: = 1 до n зробити

якщо [почати, i] = 1 

          тоді, якщо Color [i] = 0, то DFS (i)

                                 якщо Color [i] = 1, то CycleFound: = true;

   Колір [початок]: = 2;

кінець;