Wie um zu überprüfen, ob es ein Kreis in einem Baum ist?

Question

Hier ist ein Baum:

  

  

1. Es wird eine Wurzel sein.

  

2. Jeder Baumknoten hat null oder mehr Kinder.

  

3. Es ist erlaubt, dass zwei Knoten Punkte auf das gleiche Kind. Sprich, beide Knoten A   und Knoten B hat Kind C.

  

Es ist jedoch verboten, dass

  

Der Knoten A ist ein Nachkomme von Knoten B, und   Knoten B ist ein Nachkomme von Knoten A.

Ein verbotener Fall ist

  

Der Knoten A hat ein Kind Knoten C und Knoten D,

     

Beide Knoten C und D hat ein Kind Knoten E,

     

Knoten E ein Kind von A hat.

Die Frage ist, wie man diesen Kreis in einer schnellsten Art und Weise bestimmen?

UPDATE : Ich weiß, das jeden Zyklus in einem gerichteten Graphen zu finden ist. Gerade jetzt habe ich es geschafft, eine Lösung ähnlich wie Tarjan Algorithmus auszudenken.

Vielen Dank für die Kommentare.

Answer 1

Do a Tiefensuche durch den Baum. Wenn Sie zu irgendeinem Zeitpunkt einen Knoten finden, die bereits in Ihrem Rückverfolgungsstapel ist, gibt es einen Kreis.

Answer 2

können Kreise gefunden werden unter Verwendung von 2-Zeiger und sie in unterschiedlichen Abständen voran. Schließlich werden die Zeiger entsprechen, eine Schleife angibt, oder die „schneller“ wird man erreichen dann beenden. Die Frage ist in der Regel von verknüpften Listen gefragt aber nicht Bäume.