DFS DFS
Carian pertama mendalam ( DFS) ialah salah satu algoritma utama pada graf. Algoritma berjalan dalam O(N + M).
Algoritma
Sebagai permulaan, kita bermula dari atas, pertimbangkan kanak-kanak atas ini, dan jika kita tidak pernah memasukkannya, maka kita mulakan DFS daripada mereka.
|
DFS DFS
Carian pertama mendalam ( DFS) ialah salah satu algoritma utama pada graf. Algoritma berjalan dalam O(N + M).
Algoritma
Sebagai permulaan, kita bermula dari atas, pertimbangkan kanak-kanak atas ini, dan jika kita tidak pernah memasukkannya, maka kita mulakan DFS daripada mereka.
|
Graf dwipartit
Graf dwipartit - graf yang bucunya boleh dibahagikan kepada dua set supaya setiap tepi menghubungkan bucu daripada set berbeza.
Selalunya dalam konteks graf dwipartit, konsep warna bucu digunakan. Membahagikan graf kepada dua bahagian dipanggil mewarna bucunya dengan dua warna berbeza. Setiap tepi mesti menyambungkan bucu dengan warna yang berbeza.
DFS.
Algoritma
Kami mula melukis dari bucu arbitrari, yang kita lukis dalam warna arbitrari.
Apabila melepasi setiap tepi, cat bucu seterusnya dalam warna bertentangan.
Jika, semasa melelaran di atas bucu jiran, kita menjumpai bucu yang sudah dicat dalam warna yang sama dengan warna semasa, maka terdapat kitaran ganjil dalam graf, yang bermaksud ia bukan dwipartit.
|
Algoritma boleh diterangkan seperti berikut:
Diberi graf berarah dengan n bucu dan m tepi. Ia dikehendaki menomborkan semula bucunya sedemikian rupa sehingga setiap tepi mengarah dari bucu dengan nombor yang lebih rendah ke bucu dengan yang lebih tinggi.
Dalam erti kata lain, ia diperlukan untuk mencari pilih atur bucu (tertib topologi) yang sepadan dengan susunan yang diberikan oleh semua tepi graf.
Kami akan menggunakan carian depth-first (dfs(v))
Jika kami menambah bucu kami pada permulaan senarai pada masa keluar dari \(dfs(v)\) , maka pada akhirnya dalam senarai ini anda mendapat jenis topologi.
Oleh itu, isihan topologi yang diingini — ini diisih mengikut tertib menurun masa keluar.
|