Bir Çizgide Tüm Döngü Bazlarını Bul, Vertex Koordinatları Verildiğinde

Question

Benzer bir soru is posted here.

Vertex V ve Edge E ile doğrulanmamış bir grafiğim var. Bu grafikteki tüm döngü tabanlarını tanımlamak için bir algoritma arıyorum. Bu tür bir grafik örneği aşağıda gösterilmektedir: Şimdi

, her köşe koordinatlarının bilinen olan (önceki sorunun farklı , ve yukarıdaki şemada açıklama aksine) Bu nedenle, tüm grafiği kapsayan en küçük döngüleri bulmak mümkündür.

Bu grafikte, herhangi bir döngü oluşturmayan kenarların olması mümkündür.

Bunu yapmanın en iyi algoritması nedir?

Burada bakmak başka örnek:

e1 ilk aldım alır kenar olduğunu varsayarsak, ve ok kenarının yönünü gösterir.

Answer 1

Bunu denemedim ve oldukça hırslı ama çalışması gerekir: birine

Git

1. bir düğüm seçin size başlangıç ​​düğüme geri dönene kadar devam edin
2. 's komşuları en ancak eski bir düğümü ziyaret etmenize izin verilmiyor.
3. Eğer bir döngü alırsanız, önceden mevcut değilse veya bu düğümün bir alt kümesi bir döngü oluşturuyorsa kaydedin. Döngüdeki düğüm başka bir döngüdeki düğümlerin bir alt kümesiyse, daha büyük döngüyü kaldırın (veya belki ikiye bölünebilir mi?)
4. Yeni bir komşuyla 2'de baştan başlayın.
5. 1'den yeni bir düğümle baştan başlayın.

Yorumlar: 3. adımda, 2. adımdaki gibi aynı şeyi yapmalısınız, bu yüzden tüm olası yolları kullanın.

Bu bir başlangıç ​​olabilir mi? Dediğim gibi, denemedim, bu yüzden optimize edilmedi.

DÜZENLEME: Algoritmanın bir uygulamasının belgesiz ve optimize edilmemiş bir sürümü burada bulunabilir: https://gist.github.com/750015. Ancak, çözümü yalnızca "doğru" altkümeleri tanıyabildiğinden tamamen çözmez.