BaşlayınÜcretsiz Başlayın

Graflar için DFS uygulama

Bu egzersizde, bir graf üzerinde gezinmek için derinlik öncelikli arama (depth first search) algoritmasını uygulayacaksın.

Adımları hatırla:

  1. Herhangi bir düğümden (tepe) başla
  2. Bu düğümü ziyaret edilenler listesine ekle
  3. Her bir mevcut düğümün komşusu için
    • Eğer ziyaret edildiyse -> yok say
    • Eğer ziyaret edilmediyse -> özyinelemeli olarak DFS uygula

Kodunu test etmene yardımcı olmak için aşağıdaki graf bir sözlük kullanılarak yüklendi.

Graphical representation of a graph.

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

Bu egzersiz

Python'da Veri Yapıları ve Algoritmalar

kursunun bir parçasıdır
Kursu Görüntüle

Egzersiz talimatları

  • current_vertex henüz ziyaret edilmemiş mi, kontrol et.
  • current_vertex'i visited_vertices'e ekle.
  • dfs() fonksiyonunu uygun değerleri geçirerek özyinelemeli olarak çağır.

Uygulamalı interaktif egzersiz

Bu örnek kodu tamamlayarak bu egzersizi bitirin.

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')
Kodu Düzenle ve Çalıştır