Tiefensuche mit Backtracking

Hi, ich habe diesen Depth first search-Algorithmus von Wikipedia implementiert:

1  procedure DFS-iterative(G,v):
2      let S be a stack
3      S.push(v)
4      while S is not empty
5            v = S.pop() 
6            if v is not labeled as discovered:
7                label v as discovered
8                for all edges from v to w in G.adjacentEdges(v) do
9                    S.push(w)

nun möchte zusätzlich den vollständigen Laufweg ausgeben, insbesondere möchte ich den Weg zurückverfolgen, wenn ich in eine Sackgasse gekommen bin(Weg von Sackgasse bis zum nächsten möglichen abzweig).

In diesem Beispiel hätte ich also gerne die Ausgabe: 1,2,3,4,3,2,1,5,6,7,6,5,8,5,1,9,10,9,1. Weis jemand wie man das machen kann?
Falls es eine Rolle spielt: Jeder Knoten kann bis zu 6 weitere Zweige haben.

Danke!
MfG
Dudeldu

Du könntest die Punkte einer "Pfad"-Liste anfügen, wenn Du bei ihnen vorbeikommst?

Ahh ok, entschuldige bitte... Im rekursiven Algo ist das natürlich einfacher. Ich glaube, man könnte "null"-delimiter am Ende eines Knotens einfügen, dann weiß man, dass es hier eine Stufe zurückgeht. Ist aber gerade nur so aus dem Bauch heraus.

Hier ein schneller, ungetesteter Vorschlag. Geht bestimmt auch einfacher.

procedure DFS-iterative(G,v):
  let S be a stack
  S.push(v)
  currentPosition = null
  while S is not empty
    v = S.pop()
    if v is not labeled as discovered:
      label v as discovered
      while currentPosition != null and currentPosition != predecessor[v]:
        currentPosition = predecessor[currentPosition]
        print currentPosition
      print v
      currentPosition = v
      for all edges from v to w in G.adjacentEdges(v) do
        if w is undiscovered:
          S.push(w)
          predecessor[w] = v

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.