Einen Baum durchlaufen

[alzaimar]

Graphen durchlaufen, z.B. so:

Delphi-Quellcode:

Procedure Visit (aNode : TNode);
Var
  Neighbor: TNode;

Begin
  if aNode.Visited Then Exit;
  aNode.Visited := True;
  Foreach Neighbor in aNode.Neighbors do
    Visit (Child);
End;

Vorher natürlich im gesamten Graphen die 'Visited' Eigenschaft auf False setzen.
Beim Travelling Salesman Problem merkst Du dir den Startknoten und die Anzahl bereits besuchter Knoten. Wenn Du einen Knoten besuchst, dan prüfst Du einfach, ob das der Startknoten ist und ob Du alle Knoten besucht hast. Fertig.

[edit]
Ach ja, und die Gesamtentfernung berechnest Du aus der Summe der Einzelentfernungen. Man hat dafür eine 'Kosten' Funktion, hier die Entfernungen. Die Funktion Cost (a,b) liefert Dir die Entfernung zwischen a und b. Das ist einfacher, als für jeden Neighbor-Knoten die Entfernung im Node zu speichern, weil dann die Entfernungen doppelt gespeichert sind:
wenn a ein Nachbar von b ist , dann ist ja auch b ein nachbar von a...
[/edit]