2

我试图在一个无向图中列出所有路径，我的问题类似于这个问题。我试图运行这段代码，但它无限循环——我用 60 个节点运行它。关于如何产生正确解决方案的任何想法？

我添加了这样一个随机图，现在的代码如下：

    #include<stdio.h>

static struct {
  int value1;
  int value2;
  int used;
} data[] = {
  { 1, 2 },
  { 1, 5 },
  { 2, 3 },
  { 2, 6 },
  { 3, 7 },
  { 4, 0 },
  { 0, 4 },
  { 7, 3 },
  { 2, 1 },

};

enum { DATA_SIZE = sizeof data / sizeof *data };

static int output[DATA_SIZE];

int traverse(int from, int to, int depth) {
  output[depth++] = from;

  int i;
  if (from == to) {
    for (i = 0; i < depth; i++) {
      if (i) {
        printf("-");
      }
      printf("%d", output[i]);
    }
    printf("\n");
  } else {
    for (i = 0; i < DATA_SIZE; i++) {
      if (!data[i].used) {
        data[i].used = 1;

        if (from == data[i].value1) {
          traverse(data[i].value2, to, depth);
        } else if (from == data[i].value2) {
          traverse(data[i].value1, to, depth);
        }

        data[i].used = 0;
      }
    }
  }
}

int main() {
  traverse(1, 7, 0);
}`

输出为： 1-2-3-7 1-2-3-7 1-2-3-7 1-2-3-7

为什么我得到那条路径 4 次？有可能修复吗？谢谢

4

2 回答 2

3

你无法修复它。图中的路径数量（不包括稀疏图）本身就是指数级的，只有输出才会永远持续下去。显然，这是不可能的。即使您的图是稀疏的（但已连接），也至少会有 O(N^2) 条路径。

于 2013-07-29T20:34:45.820 回答
0

据我了解您链接到的算法，它将多次访问同一个顶点（但它不会多次访问同一个边）。这意味着一条路径的最大长度与图中的边数成正比，而不是与节点数成正比。你说你的图有 60 个节点——有多少条边？如果这个数字非常大，那么它可能会运行很长时间才能产生甚至一条路径。

您可以稍微修改算法以仅访问每个节点一次，但这可能不是您想要的。

于 2013-07-29T20:50:45.090 回答