Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

Graph - Breadth First search for searching an element (in Java)

807589Oct 6 2008 — edited Oct 7 2008
Hello

This is probably not a Java Coding problem but is a Programming Algorithm problem that i need to implement in Java which i cannot get.

Im sure most programmers would know that Breadth First Search (commonly known as Breadth First Traversal) goes through every element in the Graph and return a list of element(or nodes) visited. Breadth First Search mostly used for searching Graphs.

My graph is directed graph

1. Put the root node on the queue.
2. Pull a node from the beginning of the queue and examine it.
2.1. If the searched element is found in this node, quit the search and return a result.
2.2. Otherwise push all the (so-far-unexamined) successors (the direct child nodes) of this node into the end of the queue, if there are any.
3. If the queue is empty, every node on the graph has been examined -- quit the search and return "not found".
4. Repeat from Step 2.

Above algorithm is Breadth First Search in its general form - So how will i modify it so that once it has found its target node, it will:
1. Quit Search
2. Return a list of previous node that visited from root node to get to target node
(But there's a catch*)

*What i want is not return all nodes visited but the list of nodes which contains the path from root node to target node.

How?

Thanks in advance, Jason
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Nov 4 2008
Added on Oct 6 2008
27 comments
818 views