ÎncepețiÎncepe gratuit

Implementarea DFS pentru grafuri

În acest exercițiu vei implementa un algoritm de căutare în adâncime (depth first search) pentru a parcurge un graf.

Reamintește-ți pașii:

  1. Pornește dintr-un vârf oarecare
  2. Adaugă vârful în lista vârfurilor vizitate
  3. Pentru fiecare vârf adiacent nodului curent
    • Dacă a fost vizitat -> ignoră-l
    • Dacă nu a fost vizitat -> aplică DFS recursiv

Pentru a-ți testa codul, următorul graf a fost încărcat folosind un dicționar.

Graphical representation of a graph.

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

Acest exercițiu face parte din cursul

Structuri de date și algoritmi în Python

Vezi cursul

Instrucțiuni pentru exercițiu

  • Verifică dacă current_vertex nu a fost încă vizitat.
  • Adaugă current_vertex la visited_vertices.
  • Apelează dfs() recursiv, transmițând valorile corespunzătoare.

Exercițiu interactiv practic

Încearcă acest exercițiu completând acest cod de exemplu.

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')
Editează și rulează codul