图上的迭代 DFS 具有 post-visit 排序

Question

我目前正在尝试在有向图上实施 Kosaraju 算法以查找所有强连通分量。

我很清楚这个算法是如何工作的，但是我在获取 DFS 结果的 post-visit 顺序时遇到了一些问题。

目前，我的 DFS 实现的伪代码如下：

[编辑] ：我终于得到了一个 DFS 版本，其中 post 访问顺序作为输出。我考虑在每次该节点将邻居推送到 DFS 堆栈时递增一个代表该节点 "lock" 的数字。然后，当一个节点的访问结束时（没有更多的邻居可以推送），我注意到推送它的那个 child 的 DFS 结束了（我减少了它的锁）。如果这个通知也结束了前面的访问，我就到上一个前面的节点去通知，等等...

dfs(G, s):
    for all v in vertices :
        mark[v] = false
        blocked[v] = 0
        preceding[v] = -1
    mark[s] = true
    create a stack P
    P.push(s)
    while P not empty:
        v = P.pop
        for all t neighbours of v:
            if mark[t] = false:
                mark[t] = true
                blocked[v]++
                preceding[t] = v
                P.push(t)
        if no neighbours added to the stack:
            while(blocked[v] == 0):
                result.push(v);
                v = (preceding[v] == -1) ? preceding[v] : v 
                blocked[v]--

~~但我不确定这种实现是否会为 Kosaraju 算法输出正确的 post 顺序。~~

~~我的DFS对不对？~~

~~我的 DFS 示例：~~

~~（我顺时针列出了顶点，所以a = 0, b = 1, c = 2, d = 3, h = 4, g = 5, f = 6, e = 7）~~

图作为邻接表：

{0} --> {1}

{1} --> {2, 6, 7}

{2} --> {3, 5}

{3} --> {2, 4}

{4} --> {3, 5}

{5} --> {6}

{6} --> {5}

{7} --> {0, 6}

我的 DFS 的另一个问题是我的算法以降序计算邻居。我认为这并不重要，因为邻居实际上是一组顶点，但在我的例子中我遇到了奇怪的问题。

邻居计算顺序递增的解释：

输入0，开1

我弹出 DFS 堆栈（是 {0}），它 returns 0。他有 1 作为邻居，所以我将 1 压入 DFS 堆栈（现在是 {1} )

进入1，开场2 6 7

我从DFS栈中弹出1，他有2,6,7作为邻居，所以我将它们压入栈中（现在是{7,6,2}）

进入2，开场3

我从栈中弹出2（现在是{7, 6}），邻居是3和5，我压入他们，栈是{7, 6, 5, 3}

进入3，开场4

*我从栈中弹出3（现在是{7,6,5}），4是唯一的邻居，我压栈，栈是{7,6,5,4}

正在输入 4

我从堆栈中弹出 4（是 {7, 6, 5}），5 是邻居但已经 "marked" 因为是 2[= 的邻居13=]
输入 5

我从栈中弹出5，现在是{7, 6}，所有的邻居(6)都已经“标记”

输入 6

我从栈中弹出6，{7}，5已经是"marked"邻居

正在输入 7

我从堆栈中弹出 7，{empty}，邻居 (1 & 6) 已经是 "marked"

我的结果数组是 0 1 2 3 4 5 6 7 因为我的 "treated" 节点是这个顺序（或者 7 6 5 4 3 2 1 0 我的 post-visit实施）

随着邻居的计算顺序递减（我的实际 DFS），我得到：

输入0，开1

堆栈 {} -> {1}

进入1，开场7 6 2

堆栈 {} -> {2, 6, 7}

正在输入 7

堆栈 {2, 6} -> {2, 6}

进入6，开场5

堆栈 {2} -> {2, 5}

输入 5

堆栈 {2} -> {2}

进入2，开场3

堆栈 {} -> {3}

进入3，开场4

堆栈 {} -> {4}

正在输入 4

堆栈 {} -> {}

我得到了以下结果 0 1 7 6 5 2 3 4（或 4 3 2 5 6 7 1 0 对于 post 访问）

问题是，当我反转图形计算 Kosaraju 算法的最后部分时，两个结果不等价：

第一个结果（最终获得正确数量的 SCC）（堆栈 {7, 6, 5, 4, 3, 2, 1, 0}）：

Opening 0,dfs returns 1 and 7 -> 0, 1, 7在同一个SCC中，从工作栈中删除它们（现在是{6, 5, 4, 3, 2} ) 和图表。

Opening 2, dfs returns 3 and 4 -> 2, 3, 4 在同一个SCC中，从working stack（现在是{6, 5}）和graph中删除它们。

Opening 5, dfs returns 6 -> 5, 6在同一个SCC

2n 结果，堆栈 {4, 3, 2, 5, 6, 7, 1, 0}:

Opening 0,dfs returns 1 and 7 -> 0, 1, 7在同一个SCC中，从工作栈中删除它们（现在是{4, 3, 2, 5, 6} ) 和图表。

打开 6，dfs returns 5、4、3 和 2 -> 2、3、4、5、6 在同一个 SCC （但它们不在）（因为在反转图中，从 6 开始到 5 然后到 4 或 2...）

可以一个有人向我解释为什么在 DFS 中按升序或降序计算顶点与 Kosaraju 算法的结果不同吗？

~~编辑：我提供了一些关于如何获得结果以及如何手动运行算法的额外信息。希望现在更清楚了。~~

Answer 1

这是我的 DFS 获取 post 访问顺序的 C 实现，希望这对某人有所帮助：

typedef struct _graph_list {
    int nb_nodes;
    int* tab_nodes;
    int* succ_list;
} graph_list;

typedef struct _stack {
    unsigned int max_capacity;
    int* array;
    int top_position;
} stack;

int* getSuccFromList(graph_list* graph, int i){
    if (graph->tab_nodes[i] == -1) return NULL;
    int case_succ = graph->tab_nodes[i];
    int next_case_succ = graph->tab_nodes[++i];
    while (next_case_succ == -1){
        next_case_succ = graph->tab_nodes[++i];
    }
    int nb_succ = next_case_succ - case_succ;
    int j;
    int* res = malloc(sizeof(int)*(nb_succ + 1));
    for(j = 0; j < nb_succ; j++){
        res[j] = graph->succ_list[case_succ + j];
    }
    res[nb_succ] = -1;
    return res;
}

int* dfsPostVisit(graph_list* graph, int vertex){
    int i, j, nb_nodes, tmp_v;
    int* succ;
    int eof_visit;
    nb_nodes = graph->nb_nodes;
    int* res = malloc(sizeof(int)*(nb_nodes + 1));
    int* mark = malloc(sizeof(int)*nb_nodes);
    int* blocked = malloc(sizeof(int)*nb_nodes);
    int* prec = malloc(sizeof(int)*nb_nodes);
    for(i = 0; i < nb_nodes; i++){
        res[i] = -1;
        mark[i] = 0;
    blocked[i] = 0;
    prec[i] = -1;
    }
    res[nb_nodes] = -1;
    stack* s = createStack(nb_nodes);

    push(s, vertex);
    mark[vertex] = 1;
    i = 0;
    while(!isEmpty(s)){
        vertex = pop(s);
        succ = getSuccFromList(graph, vertex);  
        j = 0;
        eof_visit = 0;
        if(succ!=NULL){
            while(succ[j] != -1){
                tmp_v = succ[j++];
                if(!mark[tmp_v]){
                    mark[tmp_v] = 1;
                    blocked[vertex]++;
                    prec[tmp_v] = vertex;
                    push(s, tmp_v);
                    eof_visit++;
                }
            }
            free(succ);
        }
        if (eof_visit == 0){
            while (blocked[vertex] == 0){
                res[i++] = vertex;
                vertex = (prec[vertex] >= 0)? prec[vertex] : vertex;
                blocked[vertex]--;
            }
        }
    }
    i = 0;
    freeStack(s);
    free(mark);
    free(blocked);
    free(prec);
    return res;
}

有些东西可能需要增强，例如使用位数组作为布尔数组而不是 int 数组，但这是我的实际代码，它似乎可以正常工作。

感谢那些试图帮助我的人。

图上的迭代 DFS 具有 post-visit 排序

Iterative DFS on graph with post-visit ordering

algorithm

graph-theory

kosaraju-algorithm