如何遍历邻接矩阵？

Question

邻接矩阵表示任意树中节点之间的连接。

这是一个呈现无向图的邻接矩阵实例：

  1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 1 1 0 0
4 0 0 0 0

该矩阵表示一个图，其中节点 1 和 2 相连，1 和 3 相连，2 和 3 相连。

如何使用这种矩阵在这样的图中暴力破解所有可能路径的组合？我的意思是只选择节点 1 是一个单独的组合。那么，比如说，1-2 是一个单独的组合。1-2-3; 3-1-2。但是 1-2-3-1 是不可能的，因为重复选择了同一个节点。

那么如何使用这些规则对所有组合进行暴力破解呢？

我更喜欢 C#、C++ 或 Java 语言示例）

Answer 1

考虑到示例的限制，编写代码不会超过 40 行。

本质上，您只需继续访问与当前正在检查的节点相连的节点即可。一旦发现没有新的节点可供访问，就进行跟踪支持。

此外，您还需要一些方法来跟踪到达当前节点的路径。在示例中，我只是将此信息放入堆栈中，以防止出现内存管理问题。

#include <stdio.h>

#define N_NODES 4
#define NAME_OFFSET 1

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

int visited[N_NODES] = { 0, 0, 0, 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;

    do 
        printf("%d%s", p->node + NAME_OFFSET, (p->prev != NULL)?  "->" : "\n");
    while ((p = p->prev) != NULL);

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

int main (int argc, char *argv[]) {
    int i;
    for (i = 0; i < N_NODES; ++i) {
        visit(i, NULL);
    }
    return 0;
}

生产：

1
2->1
3->2->1
3->1
2->3->1
2
1->2
3->1->2
3->2
1->3->2
3
1->3
2->1->3
2->3
1->2->3
4

我想这就是你正在寻找的。