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

リンク先のアルゴリズムを理解しているので、同じ頂点に複数回アクセスします（ただし、同じエッジに複数回アクセスすることはありません）。これは、1 つのパスの最大長が、ノードの数ではなく、グラフのエッジの数に比例することを意味します。グラフには 60 個のノードがあると言いますが、エッジはいくつありますか? その数が非常に大きい場合、単一のパスを生成するために非常に長い時間実行される可能性があります。

各ノードに一度だけアクセスするようにアルゴリズムを少し変更することもできますが、それはあなたが探しているものではないかもしれません。

于 2013-07-29T20:50:45.090 に答える