ComenzarEmpieza gratis

Implementación de DFS para grafos

En este ejercicio, implementarás un algoritmo de búsqueda en profundidad para recorrer un grafo.

Recuerda los pasos:

  1. Empieza en cualquier vértice
  2. Añade el vértice a la lista de vértices visitados
  3. Para cada vértice adyacente del nodo actual
    • Si se ha visitado -> ignóralo
    • Si no se ha visitado -> realiza recursivamente DFS

Para ayudarte a probar tu código, se ha cargado el grafo indicado a continuación utilizando un diccionario.

Representación gráfica de un grafo.

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

Este ejercicio forma parte del curso

Estructuras de datos y algoritmos en Python

Ver curso

Instrucciones de ejercicio

  • Comprueba si current_vertex todavía no se ha visitado.
  • Añade current_vertex a visited_vertices.
  • Llama recursivamente a dfs() pasándole los valores adecuados.

Ejercicio interactivo práctico

Pruebe este ejercicio completando este código de muestra.

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 y ejecutar código