|
Graph - Breadth First search for searching a node ?
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
|
Linear Mode
