Implementação do site DFS para grafos

Neste exercício, você implementará um algoritmo de pesquisa de profundidade inicial para percorrer um grafo.

Lembre-se das etapas:

Comece em qualquer vértice
Adicionar o vértice à lista de vértices visitados
Para cada vértice adjacente do nó atual
- Se tiver sido visitado -> ignore-o
- Se não tiver sido visitado -> executar recursivamente DFS

Para ajudar você a testar seu código, o grafo a seguir foi carregado usando um dicionário.

Representação gráfica de um grafo.

graph = {

  '0' : ['1','2'],

  '1' : ['0', '2', '3'],

  '2' : ['0', '1', '4'],

  '3' : ['1', '4'],

  '4' : ['2', '3']

}

Este exercício faz parte do curso

Estruturas de dados e algoritmos em Python

Ver Curso

Instruções de exercício

Verifique se o site current_vertex ainda não foi visitado.
Adicione current_vertex a visited_vertices.
Chame dfs() recursivamente, passando a ele os valores apropriados.

Exercício interativo prático

Experimente este exercício preenchendo este código de exemplo.

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')

Editar e executar código