Algorithmus für ein Graphenproblem

Question

Ich muss die Verbundenheit von gerichteten Knoten in einer Liste überprüfen. Es handelt sich im Wesentlichen um Fragen mit jeweils 2 bis 7 Antworten. Die gewählte Antwort bestimmt die nächste Frage. Da diese Paare manuell erfasst werden, muss ich jeden möglichen Pfad auf Rückschleifen (nicht erlaubt) und Sackgassen (alle Routen müssen am END-Knoten enden) überprüfen. Hat jemand einen Tipp?

start --> n1 --- n2 --- n3 --- n4 --- end

            \  /   \      \   /       /

             n5     \      n6------ n7

              \      \     /       /

               n8----n9---n10----n11

          DIRECTION -->

Answer 1

Dies könnte das sein, wonach Sie suchen:

Prüfung, ob ein Graph azyklisch ist

Ihr END-Knoten ist das, was der Blattknoten in der Terminologie dieser Seite ist.

1. Wenn der Graph keine Knoten hat, ist er azyklisch.
2. Wenn der Graph kein Blatt hat, ist er zyklisch.
3. Wählen Sie ein beliebiges Blatt, entfernen Sie das Blatt und alle Übergänge zu ihm, gehen Sie zu Schritt 1.

Um sicherzustellen, dass es keine Sackgassen gibt: Stellen Sie einfach sicher, dass es nur einen einzigen Blattknoten gibt, bevor Sie den obigen Algorithmus anwenden.

Answer 2

Verwenden Sie eine Suche in der Breite zuerst Algorithmus, der alle Knoten, die Sie bereits besucht haben, aufzeichnet. Wenn bei der Suche nach dem nächsten zu durchquerenden Knoten einer der bereits besuchten Knoten eine Möglichkeit ist, dann ist der Graph falsch. Wenn Sie außerdem einen Knoten erreichen, für den es keinen anderen möglichen Knoten gibt, den Sie als nächstes durchqueren können, und Sie haben das Ende noch nicht erreicht, dann ist der Graph ebenfalls nicht richtig verbunden.