c - 如何找到从一个节点开始的所有简单路径？

Question

我有一个这样的图，现在我想打印出从0开始的所有路径

             0
             |
             1 
           /   \
          2 --- 3
          |    / \
          5---6---4

预期输出

All the path from 0 are:
0123465
0123645
0125634
0125643
0132564
0134652
01364
013652

我尝试画一棵树来理解这个问题。

我尝试对其进行编程:

int main(){ 
        ...

        //print  all node
        // choose the start node as 0
        int startV = 0;
        // init the path
        int path = startV;
        // init the visited array; 
        int visited[7] = {-1, -1, -1, -1, -1, -1, -1};

        Recur(g, n, 0, path, visited);
}

void Recur(Graph g, int numV, Vertex startV, int path, int *visited) {
    // DFS recursive algorithm

    // mark this node as visited
    visited[startV] = 1;

    // travel all the nodes under startV, 
    for (int i = 0; i < numV; i++) {
        // if there is an edge between node startV and node i && node i haven't visited 
        if (isEdge(newEdge(startV, i), g) && visited[i] == -1) {
            // save and print the path
            path = path * 10 + i;
            printf("path:%d\n", path);
            // recursive: repeat this, i as the startV
            Recur(g, numV, i, path, visited);
        }
    }


}

但是，我的代码只能输出这个。

path:1
path:12
path:123
path:1234
path:12346
path:123465

我认为我的访问列表和回溯方法可能存在一些问题。有人可以给我一些建议吗？谢谢!

Answer 1

您尚未“未访问”任何节点。

因此，当您回溯时，您无法沿着某个节点遵循另一条路线。我建议你添加

visited[startV] = -1;

在Recur函数的末尾。

void Recur(Graph g, int numV, Vertex startV, int path, int *visited) {

    // mark this node as visited
    visited[startV] = 1;

    //...

    // mark this node as not visited
    visited[startV] = -1;
}