查找无向图中两个节点之间的所有可能路径

Question

谁能给我一个C代码来找到两个节点之间的所有可能的路径？例如：如果图有以下边1-2 1-3 2-3 2-4 3-4

1和4之间的所有路径为：

1-2-3-4

1-2-4

1-3-4

1-3-2-4

Answer 1

深度优先搜索可以完成这项工作。

Answer 2

(我假设您不希望路径中有重复的节点-否则可能的路径数量是无限的。)

你可以放松一下：

while (there is a change) {
  for (v in nodes(G)) {
    for (e in edges(v)) {
      paths_to[v] = paths_to[v] union ((paths_to[e.to] not containing v) append v)
    }
  }
}

结果仍然可以是输入图大小的指数级。获取所有路径可能不是您想要做的事情。

Answer 3

这是一个解决问题的简单算法。这不是一个最优算法。

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

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, 4, 0);
}