1. Learn
    2. /
  2. 课程
    3. /
  3. Structuri de date și algoritmi în Python
Connected

道练习

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']
}

说明

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