iteracyjny DFS

Witam,
Potrzebuję iteracyjni gdyż przy rekurencyjnym otrzymuję Stack Overflow.
Wierzchołków jest milion - pewnie dlatego. Więc postanowiłem że przesiądę się na iteracyjne, ale tu są pewne schody. Będę potrzebował czasy przetworzenia wierzchołków - czyli te POST (funkcja f). Nawet nie tyle co czasy a ich kolejność przetwarzania. Dodam, że graf jest skierowany i nie koniecznie jest spójny, tzn może być parę podgrafów. Sam uskrobałem coś takiego i nie wiem czy jest to ok, więc Was proszę o pomoc.

 
stack <int> S;
void DFS(int u,vector<int>*T){
	int v;
	S.push(u);
	while(!S.empty()){
		v = S.top();
		marked[v]=true;
		POST.push_back(v);
		S.pop();
		EACH(i, T[v]) // dla kazdego sasiada
			if(!marked[*i])
			   S.push(*i);
			
			
	}
}

void START_DFS(vector<int> *T){
for(int i = 1; i<=n; ++i) {// n jest globaln
if(!marked[i])
DFS(i);
}

Czy kolejnośc wektora POST będzie prawidłowa?

Co rozumiesz przez kolejność przetwarzania? Nazwa POST sugeruje, że miałby być to czas po przetworzeniu wszystkich dzieci w grafie przeszukiwań. Jeśli tak ma to być rozumiane, to jest źle. POST.push_back powinieneś przenieść kilka linijek niżej.

Btw. Testowałeś w ogóle swoje rozwiązanie?

Ech, nie podoba mi się wklejanie tego kodu (jako że jest brzydki), ale może w czymś Ci pomoże.
Z tego co pamiętam, jest napisany po analizie książki Algorytmika praktyczna ....

Wady kodu:

• Niezbyt czytelny (w końcu algorytm... Oryginał był 100x gorszy)
• Korzysta ze śmiesznych makr, prawdopodobnie te makra sobie rozwiniesz z powrotem na pętle FOR.
• Ma sporo opcji których nie potrzebujesz (czas wejścia/wyjścia, rodzic, tworzenie lasu dfs) - prawdopodobnie wywalisz z tego sporo.
• To była w oryginale metoda klasy Graph<>

Zalety kodu:

• Działa (prawie na pewno)...

 
    #define FOR(X, FROM, TO) for(int X = (FROM); X <= (TO); X++)
    #define VAR(NAME, VALUE) typeof(VALUE) NAME = (VALUE)
    #define FOREACH(IT, C) for(VAR(IT, (C).begin()); IT != (C).end(); ++IT)

    vector<VertexData> verts;

    /* Przeprowadz szukanie wglab
        PARAMETRY!
        int end - korzen drzewa dfs (jeśli brak - zrób las)
        WYMAGANIA SZABLONU!
        int V.dIn - czas wejscia
        int V.dOut - czas wyjscia
        int V.dParent - numer ojca w drzewie dfs (lub -1) */
    void Dfs(int end = -1) {
        vector<int> queue(verts.size());
        int t = -1, begin = 0, left = 0;
        end == -1 ? end = verts.size() - 1 : begin = end;

        FOREACH(it, verts)
        { it->dIn = it->dOut = it->dParent = -1; }

        FOR(src, begin, end) if (verts[src].dIn == -1) { 
            queue[left++] = src;
            verts[src].dIn = ++t;
            verts[src].dOut = verts[src].edges.size(); // dOut chwilowo jako licznik

            while (left) {
                int next = queue[left - 1];
                if (!verts[next].dOut) 
                {
                    verts[next].dOut = ++t;
                    --left;
                } else {
                    next = verts[next].edges[--verts[next].dOut].src;
                    if (verts[next].dIn == -1)
                    {
                        queue[left++] = next;
                        verts[next].dParent = queue[left - 2];
                        verts[next].dOut = verts[next].edges.size();
                        verts[next].dIn = ++t;
                    }
                }
            }
        }
    }