如何遍历邻接矩阵

Question

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

这是一个表示无向图的邻接矩阵的实例:

<>之前1 2 3 410 10 11 102 1 0 1 03 1 1 0 04 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

我猜这就是你要找的。

Answer 2

看起来好像你在使用一个无向图，你可能想要一个非循环路径。

你拥有的两个最简单的选择是在图上进行广度优先或深度优先的遍历。我要做的是写一个递归方法(深度优先)，像这样:

public void recurse(int node) {
    System.out.print("-> " + node);
    for (int i = node; i < num_nodes; ++i) {
        if (i == node)
            continue;
        if (graph[node][i] > 0)
            recurse(i);
    }
}

则只需遍历节点并在每个起始节点上调用recurse(node)。