Nasıl (ispat) belirli bir düğüm/yönlendirilmiş bir grafikte TÜM döngüleri bulabilirim?

Örneğin, şöyle bir şey istiyorum:

A->B->A
A->B->C->A

ancak: B->C->B

Bildiğim kadarıyla, bunu çözmenin en iyi yolu Tarjans(veya Gabows veya Kosaraju ... aşağıda Wikipedia bağlantıya bakınız) bir grafik güçlü bir şekilde bağlı bileşenler bulmak için algoritma ile olur. Kuvvetli bağlı bileşenler ve devir eşanlamlı (ama tam olarak aynı değil).

Daha iyi bir fikir edinmek için, lütfen aşağıdaki bağlantılara bakın:

1. Tarjans algoritması Vikipedi: http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm

2. Titiz bir açıklama: http://www.ics.uci.edu/~eppstein/161/960220.html

3. Diğer ilginç bağlantılar:
   http://discuss.joelonsoftware.com/default.asp?design.4.249152.10
   http://forums.sun.com/thread.jspa?threadID=597673
   http://coding.derkeiler.com/Archive/General/comp.theory/2004-02/0468.html

4. ÇOK benzer bir soru: Best algorithm for detecting cycles in a directed graph

Şimdi link verdim, bana açıklamak için (tüm iyi cevaplar ve gerçekten stackoverflow harika bir yer haline links sonra) devam edelim.

Bazı hatırlamaya işaret eder(Bağlantı 1 alınan):
1.İki nokta, A ve B, Eğer bir yolun varsa kuvvetle bağlı Bir B ve bir yol B A.

2.Kuvvetle belirli bir tepe noktasına bağlı olan tüm köşeler kümesi grafik kuvvetle bağlı bir parçasını teşkil etmektedir.

3.İçinde birden fazla tepe noktası ile güçlü bir şekilde bağlı herhangi bir bileşen, en az bir döngüsü, self-loop bileşenler hariç içerir. (Yardım için teşekkürler Schauder, bcorso) Jens

4.Bir şekilde tek bir düğüm içine bir döngü içinde tüm köşe daraltmak istiyoruz '(Bkz bağlantılar)'. ağaç Gelecekteki herhangi bir döngü zaten ziyaret ettiğimiz noktalar içeren aynı düğüm içine katlanmış olur. Biz sonunda ne her düğüm kuvvetle bağlı bir bileşen olduğu bir ağaçtır.

5.Bunu yapmak için, her bir düğümde iki bilgi ekstra bit depolamak için. Numarası adımlar derinlik ilk arama alır ulaşacak düğüm ve en az sayıda adımlar derinlik ilk arama alır ulaşmak için herhangi bir düğüm bu düğümün kuvvetli bağlı bileşen (düğümlerden gördük şimdiye kadar).

6.Olarak yaptığımız bir derinlik ilk arama ana grafik, kullandığımız ikincil veri yapısı için bize yardımcı olup olmadığını test iki düğüm vardır "aynı" (aynı kuvvetle bağlı bileşen olarak çıkıyor) ve Ekle geçerli düğüm için ikincil yapısı doğru.

Algoritma
Sen soruyu çözmek için önemsiz değil. Burada algoritma çalışır . Tarjans nasıl

1.Bilmeniz gereken ilk şey, bir DFS yapmak zorunda olduğunu. Bir yığın uygulamak için kullanılan varsayıyorum. DFS örtüsü vardırtümgrafikte tepe noktaları.

2.Her köşe v, iki değer endeksi ve lowval ile etiketlenmiş olmalı. Endeksi sadece DFS düğüm ziyaret sırasıdır. Bu lowval ziyaretçiler dizin asgari ve DFS v yakın olan köşe dizinidir. Bu köşe sonra da yığına itilir.

3.Eğer zaten içinde değil mi eğer her köşe v, recurse erişilebilir için yığın.

4.== Tüm kapalı Endeksi pop olan bir köşe v, elementler üzerinde bu kadar kendini yığını v ve kuvvetli bağlı bileşen (döngüsü) olarak yazdırabilirsiniz.

Deneyin ve bu algoritmayı uygulamak için gidiyorum. Eğer şu anda bunu istiyorsan eğer başarırsam ve burada göndeririz.

Edit
Bu soru hala şaşırtıcı bana - Bu algoritma, bu nasıl mümkün olduğu Ancak, devir sayısı V. oldukça kafam karıştı üstel olabilir E. V doğrusal mıdır? Kendim anlamaya mümkün olmamıştır.
Bu linki görmek: hayır hakkında daha fazla bilgi için http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf ShuggyCoUk ve bilinmeyen(yahoo) tarafından verilmektedir. döngüleri.