Depth first search recursive, problem on graph[picture + code]

[mandlar suurla]

Well i got graph and i have to get path to the number what is searched. Like in example n1.dfs(visited, 15); should end on when 15 is found but it wont currently. As you can see it visits all nodes, but how would i extract from visited nodes the path.
Also when i reach end it keeps visiting sub nodes.

Full graph is here http://img19.imageshack.us/i/graphsz.png/

Node.java

package graph;

import java.util.Set;

public class Node {
	public int value;
	public Node left, right, top, bottom;
	
	public Node(int value) {
		this.value = value;
	}
	
	public void dfs(Set<Node> visited, int lookingForValue) {
		if (value == lookingForValue) {
			System.out.println("Found");
			return;
		}
		if (visited.contains(this)) {
			return;
		}
		
		visited.add(this);
		if (left != null) 	left.dfs(visited, lookingForValue);
		if (right != null) 	right.dfs(visited, lookingForValue);
		if (top != null) 	top.dfs(visited, lookingForValue);
		if (bottom != null) bottom.dfs(visited, lookingForValue);
	}
	
	@Override
	public String toString() {
		return Integer.toString(value);
	}
}

Test.java

package graph;

import java.util.HashSet;
import java.util.Set;

public class Test {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Node n1 = new Node(1);
		Node n2 = new Node(2);
		Node n3 = new Node(3);
		Node n5 = new Node(5);
		Node n4 = new Node(4);
		Node n7 = new Node(7);
		Node n8 = new Node(8);
		Node n9 = new Node(9);
		Node n10 = new Node(10);
		Node n15 = new Node(15);
		
		n1.bottom = n2; n2.top = n1;
		n2.right = n3; n3.left = n2;
		n3.right = n5; n5.left = n3;
		
		n2.left = n4; n4.right = n2;
		n4.bottom = n7; n7.top = n4;
		n7.bottom = n8; n8.top = n7;
		
		n8.right = n9; n9.left = n8;
		n9.right = n10; n10.left = n9;
		n9.bottom = n15; n15.top = n9;
		
		Set<Node> visited = new HashSet<Node>();
		n1.dfs(visited, 15);
		System.out.println(visited);
	}

}

[Campbell Ritchie]

What sort of data structure is that? It looks to me like a binary tree. So what is the algorithm for a depth first search? If you are getting the wrong result you are using the wrong algorithm. What do you mean by path? Are you going to have a linked list of nodes to the number sought? Or a String?

You will have to use the very expensive hardware I so often recommend: a Cray occupying a building the size of a cinema pencil, eraser, and sheet of paper. ?Write down how you are going to tell whether you have found a value, and how you are going to add it to a path. Since it is recursive, start with a little tree, like this one

|
|
1

Then take your recursion one level higher

  1
 / \
2   3

and work out how you are to handle something like

  1
 / \
2   null

Get that sort of thing working, and it becomes easy to scale up for recursion over any kind of tree. You can work out the depth at which you found the value, from the length of the path.

[mandlar suurla]

Campbell Ritchie wrote:What sort of data structure is that? It looks to me like a binary tree. So what is the algorithm for a depth first search? If you are getting the wrong result you are using the wrong algorithm. What do you mean by path? Are you going to have a linked list of nodes to the number sought? Or a String?

You will have to use the very expensive hardware I so often recommend: a Cray occupying a building the size of a cinema pencil, eraser, and sheet of paper. ?Write down how you are going to tell whether you have found a value, and how you are going to add it to a path. Since it is recursive, start with a little tree, like this one

|
|
1

Then take your recursion one level higher

  1
 / \
2   3

and work out how you are to handle something like

  1
 / \
2   null

Get that sort of thing working, and it becomes easy to scale up for recursion over any kind of tree. You can work out the depth at which you found the value, from the length of the path.

I am sorry that i draw the binary tree, i forgot to mention the cycles are allowed like node 5 and 10 could be connected. It needs to find path between 2 nodes, no dijkstra and A* algorithms( i dont need to find shortest). Currently my code traverses all the nodes and doesn't deal with path finding. So i tought i need Stack to hold path, but how i know which element is part of path.

[Campbell Ritchie]

Don't know offhand. It is easy enough to find the shortest path through a binary tree, but I can't remember offhand how you do it through a graph with rejoining.

Again, you will have to write down the algorithm, and convert it to pseudo-code, and show us all that. Then we can see whether your code matches it. And you will have to beware of a graph which runs like this

1→ 2→ 3
   ↑  ↓
   5← 4

. . . for obvious reasons