Модуль: Поиск в глубину. DFS


Задача

1/12

DFS: Начало (C++)

Теория Нажмите, чтобы прочитать/скрыть

Поиск в глубину DFS
Поиск в глубину (DFS) - это один из основных алгоритмов на графах. Алгоритм работает за O(N + M).
 
Алгоритм
Для начала мы запускаемся от вершины, рассматриваем детей этой вершины, и если мы никогда в них не заходили, то запускаем от них DFS.


Задача

Написать процедуру void dfs (int v), которая обходит в глубину неориентированный граф от начальной вершины S и выводит все вершины в порядке обхода, начиная с вершины S через пробел в одной строке.

В первой строчке заданы три числа N - количество вершин в графе, M - количество ребер, S - стартовая вершина. В следующих M строках подаются 2 переменные Ui и Vi, описание ребер графа. Все числа во входных данных не превышают 1000.

Вывести все вершины в порядке обхода алгоритмом DFS.

В приведенной программе, g[i][j] обозначает, что между вершинами i и j есть ребро, а в массиве used мы отмечаем заходили ли мы в эту вершину.