1. Nauka
    2. /
  2. Kursy
    3. /
  3. Struktury danych i algorytmy w Pythonie
Connected

ćwiczenie

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:

  1. Zacznij od dowolnego wierzchołka
  2. Dodaj wierzchołek do listy odwiedzonych wierzchołków
  3. 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']
}

Instrukcje

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