Mengimplementasikan DFS untuk graf

Dalam latihan ini, Anda akan mengimplementasikan algoritme depth first search untuk menelusuri sebuah graf.

Ingat langkah-langkahnya:

Mulai dari sembarang simpul (vertex)
Tambahkan simpul tersebut ke daftar simpul yang sudah dikunjungi
Untuk setiap simpul yang bertetangga dengan simpul saat ini
- Jika sudah dikunjungi -> abaikan
- Jika belum dikunjungi -> lakukan DFS secara rekursif

Untuk membantu Anda menguji kode, graf berikut telah dimuat menggunakan dictionary.

Graphical representation of a graph.

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

Latihan ini adalah bagian dari kursus

Struktur Data dan Algoritma di Python

Lihat Kursus

Petunjuk latihan

Periksa apakah current_vertex belum dikunjungi.
Tambahkan current_vertex ke visited_vertices.
Panggil dfs() secara rekursif dengan meneruskan nilai yang sesuai.

Latihan interaktif praktis

Cobalah latihan ini dengan menyelesaikan kode contoh berikut.

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

Edit dan Jalankan Kode