Iterative Tiefensuche!

brainwave81

habe hier ein kleines problem:
ich will eine rekursive dfs methode, iterativ machen. habe gelesen
das es mit "stack" gehen soll, doch leider habe ich noch kein plan wie ich das machen kann..kann mir da jemand helfen bzw. ein paar tips geben?

hier meine dfs methode:

void Dfs(Graph &g, int v) 
{ // Tiefensuche ab Knoten v
	if (!g.IsVisited(v))
	{
		g.SetVisited(v,true); 
		Visit(g,v); 
		int w = g.FirstArc(v);
		while (w != -1) {
			if (!g.IsVisited(w)) 
			Dfs(g,w); 
			w = g.NextArc(v,w);
		}
	}
}

"g" ist der graph und "v" der erste knoten!

Jester

Ja, das geht mit nem Stack:

aktueller Knoten kommt auf den Stack. Wenn Du weiter reinläufst, dann legst Du einfach den nächsten Knoten auf den Stack. Wenn Du wieder zurück willst, weil alle Knoten schon besucht sind, dann holst Du einfach den obersten Knoten vom Stack.

brainwave81

ich habs irgendwie hinbekommen aber bin mir nicht sicher ob das richtig ist!

void Dfs(graph &g, int v) 
{// Tiefensuche ab Knoten v mit STACK
		stack<int> S;		
		int w = g.FirstArc(v);
		for (int i=0; i<GetNumArcs(); i++) {
			if (!g.IsVisited(v)) 
			{
				g.SetVisited(v,true);
				S.push(v);
				do {
					S.pop();
					Visit(g,v);
					for (int j=GetNumArcs()-1; j>=0; j--) {
						if (!g.IsVisited(v)) 
						{
							g.SetVisited(v,true);
							S.push(v);
						}
					}
				} while (!S.empty());
			} 
			v = g.NextVertex(v);
		}
}

Jester

Hm, das sieht fast ein bißchen kompliziert aus. Du solltest vielleicht ein paar Invarianten einführen, die Dir das Leben erleichtern.

Der aktuelle Knoten liegt immer auf dem Stack. Wenn der Stack leer ist wurden alle erreichbaren Knoten besucht.

visit(v);
stack.push(v);
while(!stack.isEmpty())
{
  if(allChildrenVisited(stack.top()) {
    stack.pop();
  }
  else
  {
    int node = getFirstUnvisitedChild(stack.top());
    visit(node);
    stack.push(node);
  }
}

So oder so ähnlich sollte das doch funktionieren.

brainwave81

ok aber wie kann ich mir "kinder" bei graphen vorstellen? als nachfolger?!

allChildrenVisited(stack.top()): beudetet es, dass alle nachfolger von stack.top auf visited gesetzt werden müssen?

Jester

Ja, ich meine mit Kindern die Knoten, die über eine Kante erreichbar sind. allChildrenVisited soll eine Abfrage sein. Sind alle Kinder (oder auch Nachfolger) besucht? Wenn ja, dann müssen wir ja zurück => Element vom Stack nehmen, sonst gibt es mindestens einen zum aktuellen Knoten adjazenten Knoten, der noch nicht besucht wurde. Wir nehmen also einfach den ersten und machen mit dem weiter.

edit: das visited auf true setzen könnte entweder in visit passieren, oder Du baust es schnell noch dazu.

brainwave81

die visit methoden die ich jetzt implementiert habe sind diese hier:

void SetVisited(int n ,bool b);
void SetAllVisited(graph &g, bool visit);
bool IsVisited(int n);

reicht das?

Jester

Mitdenken ist durchaus erlaubt. Das genügt natürlich vollkommen.

schreib einfach da, wo im Moment der Aufruf von visit dabeisteht noch das setVisited dazu.

allChildrenVisited läßt sich auch leicht implementieren: einfach alle Nachfolger anschaun und false zurückgeben, wenn einer davon unvisited ist, sonst halt true.

Außerdem halt noch die Funktion, die eben den ersten noch nicht besuchten Nachfolger zurückgibt.

Damit sollte sich der Code eigentlich direkt einsetzen lassen.

brainwave81

teste ich mal aus..danke soweit!