Модуль: Поиск в глубину. 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 пробела.

time 1000 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Комментарий учителя

Вставьте недостающие фрагменты кода
Python
Напишите программу ниже 
def dfs(start):      
n, m, s = map(int, input().split())
Visited = [False]*(n+1)
V = [set() for i in range(n+1)]
for i in range(m):
    u, v = map(int, input().split())
    V[u].add(v)
    V[v].add(u)

dfs(s)

     

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!