Graphen durchlaufen

[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!