Apr 2011
1 / 9
Apr 2011
Jul 2011
mehmetinal
Apr '11

I'm trying to find all paths between two vertices of a directed acyclic graph using dfs. I have the following code:

[bbone=text,167]
dfs(int src, int targ) {
int i, j, w, ww = -1;
STACK s;

push(&s, src);
while (!is_empty(&s)) {
    w = pop(&s);        
    printf("%d", w);

    if (w == targ) printf("\n");

    j = 0;
    while (1) {
        ww = prev[w][j];
        if (!ww) break;
        push(&s, ww);
        j++;
        if (j >= 4) break;
    }        

}

}
[/bbone]

succ[][] is the data structure for the graph such that succ[x] contains successors of x (at most 4).

[bbone=text,168]
succ[1]=[0 0 0 0]
succ[2]=[1 0 0 0]
succ[3]=[2 0 0 0]
succ[4]=[1 0 0 0]
succ[5]=[4 2 0 0]
succ[6]=[5 3 0 0]
[/bbone]

When I run dfs(6,1), it prints
6321
521
41

instead of
6321
6521
6541

There must be a simple solution but I couldn't find it. Any ideas?

  • created

    Apr '11

  • last reply

    Jul '11
  • 8

    replies

  • 929

    views

  • 3

    users

  • 2

    links

mehmetinal
Apr '11

Thank you, it worked. But the vertices were numbered 1 to 1000, so I used an integer array.

But space complexity is something like 1000^2. If the vertices were up to 10,000 or more, that could be trouble. Also the copy operation adds to the time. Could there be a better way of doing it, maybe iteratively instead of recursively, like the first code I sent. I'm sending the recursive function I wrote last:

[bbone=text,169]
void dfs(int src, int targ, int c1[], int s) {
int w, j;
int c2[n + 2];

copy(c1, c2, s);
c2[s] = src;

if (src == targ) printc(c2, s + 1);
j = 0;
while (1) {
    w = succ[src][j];
    if (!w) break;

    dfs(w, targ, c2, s + 1);

    j++;
    if (j > 3) break;
}

}
[/bbone]

leppyr64
Apr '11

Declare c1 and s globally, then you have O(number of nodes).

mehmetinal
Apr '11

Yes, it works with one global integer array, integer s also global, and no copy operation. And space is O(number of nodes). Thanks again .

2 months later
leppyr64
Jul '11

Can you do it for a tree? I have no intentions of doing the work for you, but I will gladly help you understand what you dont.

bharti_arya22
Jul '11

i want the complete program in c that performs dfs. and there are millions of nodes in my directed graph so i want that either it take some random inputs or it take input from a file.its urgent..

leppyr64
Jul '11

en.m.wikipedia.org/wiki/Depth-first_search2

"millions of nodes" and "DFS" is not a good combination. The complexity of a DFS would leave you covering the same ground many times. You might be better suited to using Dijkstra's algorithm.

As I said in my earlier post, I will help you learn but I will not do the work for you. Unfortunately i dont work well with "urgent" because I have a full-time job and it comes first. If it's really urgent you might want to try a site like rent-acoder.com/ or ask for help at stackoverflow. If you get on those sites you will need a much more formal description of your problem.

Suggested Topics

Topic Category Replies Views Activity
Hosting a competition on SPOJ Off-topic 1 129 Apr 9

Want to read more? Browse other topics in Off-topic or view latest topics.