iterative DFS

[hell_bird]

Könnt ihr mir helfen? Gerade bringe ich keinen klaren Gedanken mehr zustande.

Ich will eine Tiefensuche der folgenden Art. Knoten sollen in einen vector geschrieben werden aber erst auf dem Rückweg.


dfs(knoten)
{
if(!visited(knoten))
{
foreach(kind von knoten)
{
dfs(kind)
}
outputvector.push_back(knoten)
}
}


Das ganze soll aber iterativ umgesetzt werden, weil ich vermeiden will, dass es zu einem stackoverflow kommen kann. Das kann doch eigentlich nicht so schwer sein. Vielleicht liegt es auch an der Uhrzeit...

//edit: habs jetzt doch hinbekommen... wer Lust hat kann mir ja Tipps geben wie man das eleganter macht. So hab ich es gerade umgesetzt

struct pmarker
{
unsigned int node;
unsigned int childpos;

pmarker(unsigned int node, unsigned int childpos) : node(node), childpos(childpos) {}
};

void dfs(StrGraph* sg, unsigned int node, vector<unsigned int> &output, bool *visited)
{
stack<pmarker> ttree;
ttree.push(pmarker(node, 0));

while(!ttree.empty())
{
while((ttree.top().childpos < sg->backwards[ttree.top().node].size())) // position < Anzahl Kinder
{
if(!visited[sg->edge_info[sg->backwards[ttree.top().node][ttree.top().childpos]].src]) // Kind Nummer <childpos> noch nicht besucht
{
ttree.push(pmarker(sg->edge_info[sg->backwards[ttree.top().node][ttree.top().childpos]].src, 0)); // Kind Nummer <childpos> auf Stack legen
}
else
{
ttree.top().childpos++;
}
}

output.push_back(ttree.top().node);
visited[ttree.top().node] = true;
ttree.pop();
if(ttree.size() > 0)
{
ttree.top().childpos++;
}
}
}