Clasificación topológica mediante DFS sin recursión.
Sé que la forma común de hacer una ordenación topológica es usar DFS con recursión. Pero como lo harías usandostack<int>
en lugar de recursion? Necesito obtener el orden posterior invertido pero estoy un poco atascado:
La grafica es unavector<vector<int> >
lista de adyacencia
El siguiente es el DFS que quiero usar para la ordenación topológica
bool visited[MAX]={0};
stack<int> dfs, postOrder;
vector<int> newVec;
vector<int>::iterator it;
for(int i=0;i<MAX;i++){
if(visited[i]==false){
dfs.push(i);
}
while(!dfs.empty()){
int node=dfs.top();
dfs.pop();
visited[node]=true;
newVec=graph[node]; //vector of neighboors
for(it=newVec.begin();it!=newVec.end();it++){
int son=*it;
if(visited[son]==false){
dfs.push(son);
}
}
}
}