《算法导论》22.3-6非递归的图的深度遍历

习题22.3-6

重写DFS,利用一个栈来消除递归

pi[u]表示u的先辈域，color[u]表示u的颜色，d[u]表示访问u的时间戳，f[u]为完成u的时间时间戳

伪代码：

Stack stack = initStack();
int time = 0;
foreach (vertex u in V[G]){
    color[u] = WHITE;
    pi[u] = NIL;
}


foreach (vertex u in V[G]){
    color[u] = GRAY;
    push(stack, u);

    while (isNotEmpty(stack) && color[peak(stack)]!= BLACK ){
       vertex cur = peak(stack);
        time++;
        d[cur] = time;
        bool finished = true;
        foreach (vertex tmp in V[cur]){
            if(color[tmp] == WHITE){
               color[tmp] = GRAY;
               pi[tmp] = cur;
               push(stack, tmp);
               finished = false;
               break;
            }
        }
        if( finished == true){
                color[cur] = BLACK;
                time++;
                f[cur] = time;
                pop(stack);
        }
    }
}