Temukan Siklus Sederhana dalam Grafik Arahan

15

Masalah ini, bagi saya, terlihat sangat menarik. Itu akan menemukan siklus sederhana (yaitu siklus di mana node tidak berulang) dalam grafik diarahkan.

Solusi saya akan seperti ini, yaitu, grafik ini adalah masalah kasus: masukkan deskripsi gambar di sini

Saya tahu bahwa ada siklus dalam grafik, ketika Anda dapat menemukan "tepi belakang" dalam pencarian mendalam-pertama (putus-putus dalam gambar saya di DFSTree), dan untuk sesaat saya dapat yakin untuk beberapa siklus, tetapi tidak untuk semua, siklus sederhana. Karena, egdes yang diarahkan sangat penting untuk dari suatu siklus, yaitu (0123)! = (0321)

Saya sedang berpikir dalam membuat dfs untuk setiap node dengan back-edge, tapi saya tidak yakin, dan itu tidak jelas. Jadi, saya bertanya kepada Anda, jika Anda membimbing saya. Terima kasih!. masukkan deskripsi gambar di sini

Berikut ini hitungan loop sederhana untuk masalah kasus saya.

masukkan deskripsi gambar di sini masukkan deskripsi gambar di sinimasukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini masukkan deskripsi gambar di sini

Jonaprieto
sumber
Saya menemukan ini stackoverflow.com/questions/2939877/…
jonaprieto

Jawaban:

13

Pertanyaan ini tampaknya sangat dapat digunakan oleh Google. Misalnya, Anda mungkin tertarik dengan algoritme yang disajikan dalam makalah ini:

Menemukan semua sirkuit dasar dari grafik yang diarahkan . Donald B. Johnson. SIAM J. COMPUT. Vol. 4, No. 1, Maret 1975

Abstrak. Algoritma disajikan yang menemukan semua sirkuit elementer-dari grafik terarah dalam waktu yang dibatasi oleh O((n + e)(c + 1))dan ruang yang dibatasi oleh O(n + e), di mana ada nsimpul, etepi dan csirkuit elementer dalam grafik. Algoritma menyerupai algoritma oleh Tiernan dan Tarjan, tetapi lebih cepat karena menganggap setiap sisi paling banyak dua kali antara setiap rangkaian dan berikutnya dalam urutan output.

Makalah ini berisi algoritma yang lengkap.

badroit
sumber
Baik. Kertas itu sempurna, tetapi bisakah saya pergi ke tempat lain dengan pekerjaan saya, atau hanya melihat kertas? Saya sedang mencari Anda memperkenalkan saya pada solusi, apa yang saya lupakan dengan ide saya?
Jonaprieto
2
Masalah utama Anda adalah bahwa dfs-tree tidak unik (mis. Bertukar "1" dengan "3" pada diagram Anda). Anda perlu melihat semua kemungkinan dfs-tree untuk menghitung semua siklus.
badroit
1
Jika Anda memerlukan implementasi Java dari algoritma ini: github.com/1123/johnson
user152468
Tautan @badroit rusak ... :(
Jorge E. Hernández
@ Longongooo, terima kasih ya, saya menggantinya.
badroit