Обход графа в глубину (см. ru.wikipedia.org)

Пусть задан граф G = (V,E), где V — множество вершин графа, E — множество ребер графа. Предположим, что в начальный момент времени все вершины графа окрашены в белый цвет. Выполним следующие действия:
  1. Из множества всех белых вершин выберем любую вершину, обозначим её v1.
  2. Выполняем для неё процедуру DFS(v1).
  3. Перекрашиваем её в чёрный цвет.
  4. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.
Процедура DFS (параметр — вершина u)
  1. Перекрашиваем вершину u в серый цвет.
  2. Для всякой вершины w, смежной с вершиной u, выполняем следующие два шага:
    1. Если вершина w окрашена в белый цвет, выполняем процедуру DFS(w).
    2. Окрашиваем w в чёрный цвет.
Граф контрольного примера (файл input.txt) приведён на рисунке: dfs_graph.jpg not found,