I'm trying to find all the paths between node 1 and node 12. The only restriction is that I cannot traverse any path between two nodes more than once. Currently, my program just works in the forward direction. I need to consider paths such as 1 > 2 > 5 > 3 > 2 > 6 > 8 > 11 > 12, where the program travels back to a node. The counter is just there to count the number of paths available (there should be 640 total paths, but I only have 16 paths). This is what I have so far. Any ideas?
#include <stdio.h>
int edges[12][12] = {
{0,1,0,0,0,0,0,0,0,0,0,0},
{1,0,1,1,1,1,0,0,0,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0},
{0,1,0,0,1,0,0,0,0,0,0,0},
{0,1,1,1,0,0,1,1,0,0,0,0},
{0,1,0,0,0,0,0,1,0,0,0,0},
{0,0,0,0,1,0,0,0,0,0,1,0},
{0,0,0,0,1,1,0,0,1,1,1,0},
{0,0,0,0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,0,1,0,0,1,0},
{0,0,0,0,0,0,1,1,1,1,0,1},
{0,0,0,0,0,0,0,0,0,0,1,0}
};
int visited[12] = {0,0,0,0,0,0,0,0,0,0,0,0};
int counter = 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;
if (node == 1){
printf("%s", "1->");
}
if (node == 1){
do
printf ("%d%s", p->node + 1, (p->prev != 0)? "->" : "\n");
while ((p = p->prev) != 0);
}
if (node == 1){
counter++;
printf("%d\n", counter);
}
visited[node]=1;
int i;
for (i=0; i<12; ++i){
if ((visited[i] == 0) && (edges[node][i] == 1))
visit (i, &n);
visited[node]=1;
}
visited[node]=0;
}
int main (int argc, char *argv[]) {
int i;
for (i=11; i<12; ++i) {
visit (i, 0);
}
return 0;
}