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


Задача

1/19

DFS: Начало (Python)

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

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


Задача

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

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

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

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