OJ Board

hello,

i am interested in learning the exhaustive BFS algorithm. using this algorithm some one has solved the "the game " problem.

So, please help me by providing useful resourses.

thanks.

breadth first search(algorithm)

Definition: A search algorithm which considers neighbors of a vertex, that is, outgoing edges of the vertex's predecessor in the search, before any outgoing edges of the vertex. Extremes are searched last. This is typically implemented with a queue

Get the idea?

More information at http://www.nist.gov/dads/HTML/breadthfirst.html

Thank you ming for your reply. But let me know how this exhaustive BFS algorithm can be used for finding shortest paths in wieghted graph?

wieghted graph?:: I don't understand yuor question.

Here is something:
queue is first in, first out while
stack is first in, last out.

Generally, you make use of a queue to do bfs.

[cpp]
queue q;
q.push(INITIAL_STATE);
while (q.size()) {
STATE x=q.front(); q.pop();
process(x);
}[/cpp]

The function process must produce more states. We must ensure that states are not repeated and that varies from problem to problem. States must also be stored efficiently. That is also dependent on the problem.

BFS is usually used for maze problems like acm 429, 652.

Yes, the BFS can be used to find the shortest path in a weight graph. However, if the graph contains no negative edges, it is probably easier and more efficient to consider using Floyd-Warshall.

BFS on a weight graph is basically.
Start at a vertex.
Are any of the vertices connected to this one the target vertex, if so, is the distance traveled less than the minimum distance?
Run BFS with each of the connected vertices as the starting vertex.

But, heed my advice, Floyd-Warshall is better.

in weighted grafs, its the same thing

execept that u choose the next node with the less weight,
and not the first it was found.

I do agree that Floyd is easier to implement than BFS, but the n^3 running time really makes it unsuitable in some occasions. For example, try solving 532 using floyd...you get my point.

By the way, I thought only Dijkstra cannot work with negative edges? Floyd cannot work too? I'm really not sure

[/i]

Floyd fails for negative cycles and Dijkstra fails for negative edges. Sorry...

Hi, I need to learn 'exhaustive bfs', any discussion on this topic will a great help... can you provide me with some good links? If the basic idea is presented with some pseudocode, I hope to fill the rest