Saya memiliki pseudocode berikut untuk algoritma pencarian luas-pertama
BFS(G,s)
1 for each vertex u ∈ V(G) \ {s}
2 color[u] = white
3 d[u] = ∞
4 π[u] = nil
5 color[s] = gray
6 d[s] = 0
7 π[s] = nil
8 Q = ∅
9 Enqueue(Q,s)
10 while q ≠ ∅
11 u = Dequeue(Q)
12 for each v ∈ Adj[u]
13 if color[v] == white
14 color[v] = gray
15 d[v] = d[u] + 1
16 π[v] = u
17 Enqueue(Q,v)
18 color[u] = black
Saya tidak mengerti apa yang ditunjukkan huruf π dalam konteks ini. Saya tidak terbiasa dengan algoritma ini dan sulit ditebak.
Saya pikir dmenunjukkan jarak, colortentu saja warnanya, tapi itu π... tampaknya menjadi semacam variabel tapi saya tidak mengerti fungsinya dalam kodesemu ini.
Jawaban:
Saya percaya penggunaan π di sini adalah "orang tua" yang sebenarnya. Jadi dalam hal ini, "induk" dari v adalah kamu karena kita sedang melihat semua simpul yang berdekatan dengan kamu .
sumber
Vektor π pasti membuat simpul u yang Anda gunakan untuk simpul v. Ini membantu ketika Anda harus membangun pohon BFS dari grafik. Meskipun tidak perlu, teknik ini mengurangi banyak kerumitan ketika Anda harus melakukan lebih banyak waktu BFS (mis. Algoritma Edmonds-Karp untuk menghitung aliran maksimum antara dua node dalam grafik). Dalam hal ini Anda tidak perlu menjalankan BFS lebih banyak karena Anda sudah memiliki pohon BFS yang dibangun dan lintasi dari daun ke root.
sumber