Программа C для поиска в глубину или DFS для графика

Обход в глубину (или поиск) для графа аналогичен обходу в глубину дерева. Единственная загвоздка здесь в том, что, в отличие от деревьев, графы могут содержать циклы, поэтому мы можем снова прийти к одному и тому же узлу. Чтобы избежать обработки узла более одного раза, мы используем логический массив посещений.

Например, на следующем графе мы начинаем обход с вершины 2. Когда мы приходим к вершине 0, мы ищем все соседние с ней вершины. 2 также является смежной вершиной с 0. Если мы не отметим посещенные вершины, то 2 будет обработана снова, и это станет незавершающим процессом. Обход в глубину следующего графа равен 2, 0, 1, 3.

См. этот пост для всех приложений обхода в глубину.
Ниже приведены реализации простого обхода в глубину. Реализация C++ использует представление графов в виде списка смежности. Контейнер списка STL используется для хранения списков соседних узлов.