Çok seviyeli referanslarda ve bağımlılıklarda dairesel mantığı veya özyinelemeyi nasıl tespit ederim

Question

Böyle bir çok seviyeli bağımlılık grafiğim var ve bu grafikte herhangi bir dairesel referansı tespit etmem gerekiyor.

, A = B

B = C

C = [D, B]

D = [C, A]

biri gibi bir problem var mı?

Herhangi bir çözüm ???

Teşekkürler ve özür dileriz.

========= güncellenen ==========

başka durum vardı.

2 = 1

3 = 2

4 = [2, 3]

5, bu durumda, = 4

, benim özyinelemeli kod yineleme iki "4" referansındaki zamanlar, ancak bu referanslar sonsuz bir döngü oluşturmaz. Benim problemim, fonksiyonun bir kereden fazla bir referansı yinelemesi ve sonsuz döngü olmaması ve sonsuz bir döngü olduğunda kullanıcıyı bilgilendirmek olduğunu bilmek.

1 = 4

2 = 1

3 = 2

4 = [2, 3]

5 = 4

Bu durum biraz ayrılmakta 2. örnek Bu sonsuz bir döngü oluşturur. Davaların sonsuz bir döngü oluşturup oluşturmadığını nasıl bilebilirim?

Answer 1

Benzersiz olarak tanımlanmış düğümlerin listesini saklayın. Tüm ağaç boyunca döngü boyunca döngüsünü deneyin, ancak bir düğümün, benzersiz listede zaten var olan bir çocuk olarak adlandırılıncaya kadar listedeki düğümleri kontrol etmeye devam edin - oradan alın (döngüyü tutun veya yalnızca gereksinim)

Answer 2

Topological sorting. Wikipedia'daki açıklama açıktır ve tüm örnekleriniz için çalışır.

Temel olarak bağımlılığı olmayan bir düğümü başlatır, sıralanmış düğümler listesine yerleştirir ve sonra bu bağımlılığı her düğümden kaldırırsınız. Sizin için ikinci örnek, 1. ile başlayacağınız anlamına gelir. Tüm bağımlılıkları 1'e kaldırdığınızda, 2 ile kalırsınız. Sonuçta onları 1,2,3,4,5 sıralamanız ve döngü olmadığını görmeniz gerekir.

Üçüncü örneğinizde, her düğümün bir bağımlılığı vardır, bu yüzden başlamak için bir yer yoktur. Böyle bir grafik en az bir döngü içermelidir.