Implementacja DFS dla grafów

W tym ćwiczeniu zaimplementujesz algorytm przeszukiwania w głąb (depth first search) służący do przechodzenia po grafie.

Przypomnij sobie kroki:

Zacznij od dowolnego wierzchołka
Dodaj wierzchołek do listy odwiedzonych wierzchołków
Dla każdego sąsiedniego wierzchołka bieżącego węzła:
- Jeśli był już odwiedzony -> zignoruj go
- Jeśli nie był jeszcze odwiedzony -> wykonaj DFS rekurencyjnie

Aby ułatwić testowanie kodu, poniższy graf został wczytany za pomocą słownika.

Graficzna reprezentacja grafu.

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

To ćwiczenie jest częścią kursu

Struktury danych i algorytmy w Pythonie

Zobacz kurs

Instrukcje do ćwiczenia

Sprawdź, czy current_vertex nie był jeszcze odwiedzony.
Dodaj current_vertex do visited_vertices.
Wywołaj dfs() rekurencyjnie, przekazując odpowiednie wartości.

Interaktywne ćwiczenie praktyczne

Spróbuj tego ćwiczenia, uzupełniając ten przykładowy kod.

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

Edytuj i uruchom kod