• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Tim Cooke
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Devaka Cooray
  • Jeanne Boyarsky
Saloon Keepers:
  • Jesse Silverman
  • Stephan van Hulst
  • Tim Moores
  • Carey Brown
  • Tim Holloway
Bartenders:
  • Jj Roberts
  • Al Hobbs
  • Piet Souris

Need help in DFS traversal

 
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
After I resolved BFS I thought I'd try my hand at DFS, with the same problem declaration: After using DFS on some kind of graph, output ith node in order with where they were visited from. For example, if the tree was just 0 1, the output would be: -1 0. On the other hand, if it was 0-2-1, the output would be: -1 2 0.

Here is my code:



sample input:
7 10
0 1
2 0
0 3
1 4
4 3
2 3
5 2
6 3
4 6
6 5

output: -1 4 3 0 6 2 5
expected: -1 0 3 4 1 2 5

any help?
 
Saloon Keeper
Posts: 24511
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Actually, a simpler way to do Depth-First Search (DFS) in Java is to do it via recursive calls to the search. That way instead of having to maintain your own stack manually, you exploit the method calling stack.

It's not only simpler to code, but when done properly the compiler can apply tail recursion optimizations to the bytecode production, making it quite efficient.
 
Jack McGonnell
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried it before but the answer was hard to store and difficult to work with (and output still incorrect, too short):

 
Tim Holloway
Saloon Keeper
Posts: 24511
167
Android Eclipse IDE Tomcat Server Redhat Java Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you're traversing a Directed Acylic Graph (a/k/a a Tree), you don't need to keep a tally of visited nodes, since a proper scan should only be visiting each node once anyway.

If, on the other hand, your graph does have shared nodes, you can log them in a Map. That would work better than an integer array, I think.
 
Jack McGonnell
Greenhorn
Posts: 14
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
in the problem, it's stated I should check when I pop the stack. There are repeated nodes used for visit, and I'm not sure map is necessary as when I print it out it has to be in order anyways (ith node was visited from X location vs 0: -1, 1: 0, etc.)
 
Bartender
Posts: 4672
183
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I had a look at your recursive latest DFS method. There are some problems with it:

1) Suppose we have the (directed or undirected) graph 0 - 2 - 1, and we do: DFS(0). The first time we enter the DFSUtli method, we have v = 0, adj = {2}. In the while loop this is then being done: seen[0] = 2. Thn we enter DFSUtils agin, wih v = 2 and adj = {1} (0 is not considered, since it is already visited). So now we get: seen[2] = 1. We're done now, we make seen[0] equal to -1 and so we print: -1 0 1, which is no good. Coming back to the line in the while loop: seen[v] = n. That is wrong as we saw, but also the reverse is false. Say v = 0. n = 9, we then get: seen[9] = 0, whick is very likely also not true. Conclusion is: seen must be filled in the index order: 0, 1, 2, 3, ..., V, whick is usually different from the vertex number we're dealing with.

A simple remedy is not to use an array for seen, but a List to which you can add the vertices. And when you're done, you can simply insert -1 at position 0

2) another disadvantage with using an array for seen, is that you may have 10 vertices, but only two vertices connected. Your seen array will show up 8 0's then, instead of showing just two vertices (starting with -1).

 
reply
    Bookmark Topic Watch Topic
  • New Topic