Začněte nyníZačněte zdarma

Implementace DFS pro grafy

V tomto cvičení implementuješ algoritmus prohledávání do hloubky pro procházení grafu.

Připomeň si jednotlivé kroky:

  1. Začni v libovolném vrcholu
  2. Přidej vrchol do seznamu navštívených vrcholů
  3. Pro každý sousední vrchol aktuálního uzlu:
    • Pokud už byl navštíven -> ignoruj ho
    • Pokud ještě navštíven nebyl -> rekurzivně proveď DFS

Pro testování kódu byl načten následující graf pomocí slovníku.

Grafické znázornění grafu.

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

Toto cvičení je součástí kurzu

Datové struktury a algoritmy v Pythonu

Zobrazit kurz

Pokyny k cvičení

  • Zkontroluj, jestli current_vertex ještě nebyl navštíven.
  • Přidej current_vertex do visited_vertices.
  • Zavolej dfs() rekurzivně a předej jí odpovídající hodnoty.

Interaktivní cvičení na vyzkoušení si v praxi

Vyzkoušejte si toto cvičení dokončením tohoto ukázkového kódu.

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')
Upravit a spustit kód