• Post Reply Bookmark Topic Watch Topic
  • New Topic

Depth first search of an adjacency list java  RSS feed

 
Dumidu Udayanga
Greenhorn
Posts: 11
Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Below is the function, which I am stuck on. I know I need to set it up in a way, which I can call dfs() again. As it is, it finds some of the connected edges when I increment v also, but it misses edge 3,1 and 4,0 which are edges with initial node having a higher index than the one it is mapped to. void dfs(int v){

 
Campbell Ritchie
Marshal
Posts: 56225
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

I think you have fallen into the trap of trying to work out how to do it before you have completely worked out what you are doing. You haven't explained how the search is supposed to operate. Please start, however, by tidying up your code. You have code difficult to read, with single‑letter variables, with variable names with CapitalLetters, with arrays of Lists (‍), wrongly‑placed [], incoirrect indentation and {}. You need to sort that out before you can read your own code, never mind show it to somebody else. As it stands, the code is definitely confusing.
Once you have done that, maybe you will have found the error for yourself; if so please tell us what you found. Otherwise, please write down an explanation of how your graph works and how you search it.
 
Piet Souris
Rancher
Posts: 2020
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi Dumidu,

welcome to the ranch!

Before talking about all things DFS, can you explain why you use such a complicated way to store your Graph-data? Is this some sort of assignment?

A much simpler approach would be to use a Map<Integer, List<Integer>>, where the keys are the vertices, and the List contains the vertices to which the key is connected.

Hope to hear!
 
Piet Souris
Rancher
Posts: 2020
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can't beat Campbell on speed...     
 
Campbell Ritchie
Marshal
Posts: 56225
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:Can't beat Campbell on speed...     
I was lucky that time 47″ faster.
Better luck next time.
 
Campbell Ritchie
Marshal
Posts: 56225
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dumidu Udayanga wrote:. . .
Will that actually compile?
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I doubt it. You can't make an array of parameterized types.
 
Piet Souris
Rancher
Posts: 2020
75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That was what I thought too. But running the code (with a quickly made dfs method) it ran without any problem.
What does NOT compile is:

with the message: "generic array creation".
But works a treat.
 
Stephan van Hulst
Saloon Keeper
Posts: 7932
143
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Right. Either way, declaring a variable that's an array of a generic type is a bad idea. I would prefer Piet's solution of using a Map, although I would replace List with Set.
 
Campbell Ritchie
Marshal
Posts: 56225
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Piet Souris wrote:. . . What does NOT compile is:  . . . message: "generic array creation". . . . .
No, you are not allowed to create an array of parametrised types; it is explained in the Java™ Tutorials. It has to do with a conflict between the covariant types in arrays and invariant types in generics. The second example with a raw type doesn't have that problem; it does however have the worse problem that this will probably also compile:-
G[0] = new LinkedList<String>();
which will produce a nice array store exception at runtime.

I don't know whether this is the right Java™ Tutorials section.
 
Campbell Ritchie
Marshal
Posts: 56225
171
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, it is this Java™ Tutorials section.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!