如何遍历邻接矩阵？

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语言的代码示例）

- EngineerSpock

---

一个简单的递归就可以解决问题。标记已经访问过的节点，以便不再访问它们。顺便说一下，图不一定是树形结构，你的例子就不是。 - Henry

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

我想这就是你在寻找的内容。 在it技术方面，我猜这就是你想要的。

- mikyra

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)。希望这可以帮助您。

- Mike T