mengapa urutan tiang yang meningkat tidak memberikan simpul tenggelam (simpul dalam komponen tenggelam yang terhubung kuat dari DAG grafik yang sesuai) dalam grafik?

Membaca tentang graf.. dikatakan bahwa setiap graf adalah graf asiklik berarah DAG dari komponen-komponen yang terhubung kuat. Oleh karena itu untuk menemukan komponen-komponen yang terhubung kuat ini kita perlu menemukan node di bagian wastafel grafik.. sekarang untuk menjelaskan lebih lanjut saya perlu menjelaskan posting no dan pra no..

pre no :- Preordering adalah daftar simpul dalam urutan pertama kali dikunjungi oleh algoritma pencarian depth-first. oleh karena itu sesuai pra no.

Demikian pula no posting: - Postordering adalah daftar simpul sesuai urutan kunjungan terakhirnya oleh algoritma DFS. pos yang sesuai no

sekarang postingan tertinggi memberikan simpul sumber (benar-benar dipahami) tetapi mengapa urutan postingan yang meningkat tidak memberikan bagian yang tenggelam?

keraguan saya adalah: - mengapa kita perlu membalikkan grafik untuk menemukan sink sehingga menemukan komponen yang terhubung. mengapa tidak dalam grafik yang sama kita menjalankan algo dalam urutan no pos yang meningkat (karena no pos terendah berada di komponen yang terhubung ke wastafel)..

Mengapa kita perlu membalik grafiknya?


graph algorithm graph-algorithm depth-first-search
person user770914    schedule 21.10.2012    source sumber

Jawaban (2)


arrow_upward
1
arrow_downward

Hal ini disebabkan oleh karakteristik komponen-komponen yang terhubung kuat. dikatakan bahwa setiap node dari komponen harus menjangkau setiap node komponen lainnya. dengan DFS pertama Anda menemukan semua node yang dapat dijangkau oleh sebuah node. dfs dari grafik terbalik memberi Anda semua node tempat node dapat diakses.

untuk menemukan komponen lengkap, penting untuk mengandalkan stempel waktu dari dfs pertama.

ada juga algoritma lain untuk mencari komponen yang terhubung kuat, yang menurut saya lebih mudah dipahami. salah satunya adalah algoritma kosarajus. lihat saja.

semoga jawabanku benar dan itu membantu :)

person Matthias Kricke    schedule 10.11.2012

arrow_upward
0
arrow_downward

Karena nomor postingan paling bawah bahkan bisa ada di sumber SCC. Bayangkan sumber SCC (SCC1) menjadi ring/loop dari 3 node, a,b&c, di mana sebuah edge menghubungkan a ke SCC lain (SCC2) yang tidak perlu kita ketahui detailnya. a,b,&c tidak mempunyai sisi lain. Jika DFS berpindah dari a ke b ke c kemudian melintasi tepi dari a ke SCC2. Dalam hal ini, nomor pos terendah dalam grafik adalah c, yang jelas merupakan node SCC sumber dan bukan node SCC sink.

person Bhavika Khare    schedule 13.01.2021