Graphen durchlaufen

[am Ende]

Hallo Forum

Ich habe einen gerichteten Graphen, dieser kann kann Zyklen beinhalten, muss aber nicht. Nun soll ich von denjenigen einem Identifizierbaren Teil der Knoten (beim Baum wären es Wurzeln) alle der Richtung nach alle Knoten durchlaufen, bis ich alle 'Endknoten' erreicht habe (beim Baum Blätter). ich kann dabei identifizieren, was Startknoten sind, was Endknoten sind, und ob der Graph Zyklen enthält. Ich kann den Graphen aber nicht splitten.

Hat mir jemand einen Hinweis, wie ich dies bewerkstelligen könnte? Solange es keine Knoten mit zwei augehenden Kanten gibt, ist mir klar wie ich das machen kann, einfach rekursiv den nächsten Knoten finden. Was aber, wenn ich mehrere ausgehende Kanten habe?

Kennt Ihr Webseiten, die sich mit sowas befassen und etwas taugen?

Besten Dank für Eure Hilfe.
Das Ende

[wahsaga]

hi,

ich kann dabei identifizieren, was Startknoten sind, was Endknoten sind, und ob der Graph Zyklen enthält. Ich kann den Graphen aber nicht splitten.

Hat mir jemand einen Hinweis, wie ich dies bewerkstelligen könnte? Solange es keine Knoten mit zwei augehenden Kanten gibt, ist mir klar wie ich das machen kann, einfach rekursiv den nächsten Knoten finden. Was aber, wenn ich mehrere ausgehende Kanten habe?

dann ist die aufgabe "bewege dich von diesem aktuellen startknoten zum knoten x" eben zwei mal durchzuführen, für zwei unterschiedliche knoten x.

entweder rekursiv, oder evtl. auch per backtracking.

gruß,
wahsaga

[Frank Schönmann]

hi!

Hat mir jemand einen Hinweis, wie ich dies bewerkstelligen könnte? Solange es keine
Knoten mit zwei augehenden Kanten gibt, ist mir klar wie ich das machen kann,
einfach rekursiv den nächsten Knoten finden. Was aber, wenn ich mehrere
ausgehende Kanten habe?

Die beiden gebräuchlichen Methoden, um Graphen zu traversieren, sind Breitensuchen
(breadth first search) und Tiefensuche (depth first search). Die sollten zb. in jedem
ordentlichen Algorithmenbuch erklärt sein. Ich empfehle "Introduction to Algorithms"
von Cormen (steht wohl in fast jeder Informatik-Bibliothek).

Um zu verhindern, dass du in zyklischen Graphen in eine Endlosschleife gerätst, musst
du die bereits besuchten Knoten irgendwie markieren oder zwischenspeichern, um sie
ab dem zweiten Besuch zu ignorieren.

bye, Frank!