c - 在 C 的邻接矩阵中回溯？

Question

我试图找到节点 1 和节点 12 之间的所有路径。唯一的限制是我不能多次遍历两个节点之间的任何路径。目前，我的程序只是在前进的方向上工作。我需要考虑诸如 1 > 2 > 5 > 3 > 2 > 6 > 8 > 11 > 12 之类的路径，其中程序返回到一个节点。计数器只是用来计算可用路径的数量(总共应该有 640 条路径，但我只有 16 条路径)。这是我到目前为止所拥有的。有任何想法吗？

#include <stdio.h>

int edges[12][12] = {
    {0,1,0,0,0,0,0,0,0,0,0,0},
    {1,0,1,1,1,1,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,1,1,0,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,1,0},
    {0,0,0,0,1,1,0,0,1,1,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,1,1,1,1,0,1},
    {0,0,0,0,0,0,0,0,0,0,1,0}
};


int visited[12] = {0,0,0,0,0,0,0,0,0,0,0,0};

int counter = 0; 


struct Node {
    int node;
    struct Node *prev;
};


void visit (int node, struct Node *prev_node) { 
    struct Node n = { node, prev_node };
    struct Node *p = &n;
    if (node == 1){
        printf("%s", "1->");
    }
    if (node == 1){
        do 
            printf ("%d%s", p->node + 1, (p->prev != 0)?  "->" : "\n");
        while ((p = p->prev) != 0);
    }
    if (node == 1){
        counter++; 
        printf("%d\n", counter);
    }

    visited[node]=1;
    int i;
    for (i=0; i<12; ++i){
        if ((visited[i] == 0) && (edges[node][i] == 1))
            visit (i, &n);
            visited[node]=1;
    }
    visited[node]=0;

}


int main (int argc, char *argv[]) {

    int i;
    for (i=11; i<12; ++i) {
        visit (i, 0);
    }
    return 0;
}

Answer 1

最大的错误是您的要求是最多访问每条边一次，但您正在跟踪节点。

此外，我建议始终在 if、while 等之后使用 {} 大括号。您的代码中有一些误导性的空格发布。

GCC 4.7.3: gcc -Wall -Wextra backtrace.c

#include <stdio.h>

int edges[12][12] = {
    {0,1,0,0,0,0,0,0,0,0,0,0},
    {1,0,1,1,1,1,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,0,0,1,0,0,0,0,0,0,0},
    {0,1,1,1,0,0,1,1,0,0,0,0},
    {0,1,0,0,0,0,0,1,0,0,0,0},
    {0,0,0,0,1,0,0,0,0,0,1,0},
    {0,0,0,0,1,1,0,0,1,1,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,0,1,0,0,1,0},
    {0,0,0,0,0,0,1,1,1,1,0,1},
    {0,0,0,0,0,0,0,0,0,0,1,0}
};

int visited[12][12] = {
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0},
    {0,0,0,0,0,0,0,0,0,0,0,0}
};

int counter = 0;


struct Node {
    int node;
    struct Node *prev;
};

void print(struct Node* p) {
    do
        printf ("%d%s", p->node + 1, (p->prev != NULL)?  "<-" : "\n");
    while ((p = p->prev) != NULL);
    printf("%d\n", ++counter);
}

void flag(int i, int j) {
  visited[i][j] = visited[i][j] ? 0 : 1;
  visited[j][i] = visited[j][i] ? 0 : 1;
}

void visit (int first, int last, struct Node *prev_node) {
    struct Node n = { first, prev_node };

    if (first == last){ print(&n); return; }

    int i;
    for (i=0; i<12; ++i){
        if ((visited[first][i] == 0) && (edges[first][i] == 1)) {
            flag(first, i);
            visit(i, last, &n);
            flag(first, i);
        }
    }
}


int main (int argc, char *argv[]) {

    visit (0, 11, NULL);
    return 0;
}