Реализация поиска в глубину для графов

В этом упражнении вы реализуете алгоритм поиска в глубину для обхода графа.

Вспомните шаги:

Начните с любой вершины
Добавьте вершину в список посещённых
Для каждой смежной вершины текущего узла:
- Если она уже посещена -> пропустите её
- Если она ещё не посещена -> рекурсивно выполните поиск в глубину

Для проверки кода следующий граф загружен в виде словаря.

Graphical representation of a graph.

graph = {
  '0' : ['1','2'],
  '1' : ['0', '2', '3'],
  '2' : ['0', '1', '4'],
  '3' : ['1', '4'],
  '4' : ['2', '3']
}

Это упражнение является частью курса

Структуры данных и алгоритмы на Python

Посмотреть курс

Инструкции к упражнению

Проверьте, что current_vertex ещё не был посещён.
Добавьте current_vertex в visited_vertices.
Вызовите dfs() рекурсивно, передав ей необходимые значения.

Интерактивное практическое упражнение

Попробуйте выполнить это упражнение, дополнив этот пример кода.

def dfs(visited_vertices, graph, current_vertex):
    # Check if current_vertex hasn't been visited yet
    if current_vertex not in ____:
        print(current_vertex)
        # Add current_vertex to visited_vertices
        ____.add(____)
        for adjacent_vertex in graph[current_vertex]:
            # Call recursively with the appropriate values
            ____(____, ____, ____)
            
dfs(set(), graph, '0')

Редактировать и запускать код