Hey there!
I'm using DFS to search how many paths do I have from vertex1 to vertex2 in a DAG graph... But I have a problem that I search the vertexes a "infinity" of times... I went here and I didn't quite understood the language or the ideas... Like "If vertex w is unexplained then"...
So here's my code
Code:
typedef struct node {
int v;
struct node *next;
} Node;
typedef Node *ADJ;
int n_paths(int vertex1, int vertex2) {
int n = 0;
ADJ temp;
temp = graph[vertex1];
if(vertex1 == vertex2)
return 1;
while(temp != NULL) {
n = n + n_paths(temp->v, vertex2);
temp = temp->next;
}
return n;
}
I ommited a big part of the code because I think this is the most important part... Any ideas how to optimize?
Thnx!