CODEWITHSUNDEEP
c++
user2147241
user2147241

Reputation: 53

Path finding in an undirected graph

I'm trying to list all the paths in an undirected graph, and my question is similar to this question. I've tried to run this code, but it loops indefinitely -- I ran it with 60 nodes. Any ideas on how to produce the correct solution?

I added such a random graph and the code is now like:

    #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);
}`

And the output is: 1-2-3-7 1-2-3-7 1-2-3-7 1-2-3-7

Why do I get that path 4 times? Is it possible to fix? thanks

Upvotes: 2

Views: 1877

Answers (2)

JoshG79
JoshG79

Reputation: 1687

As I understand the algorithm you link to, it will visit the same vertex multiple times (it will not visit the same edge multiple times, though). This means that the maximum length of one path is proportional to the number of edges in your graph, not the number of nodes. You say your graph has 60 nodes - how many edges? If that number is very large, then it may run for a very long time to produce even a single path.

You could modify the algorithm slightly to only visit each node once, but that may not be what you're looking for.

Upvotes: 0

sasha.sochka
sasha.sochka

Reputation: 14715

You can not fix it. The number of paths in graph (not counting sparse graphs) is exponential by itself and only outputting will take forever. Clearly, it's impossible. Even if your graph is sparse (but connected) there will be at least O(N^2) paths.

Upvotes: 3

Related Questions