Provide resource for exhaustive BFS algorithm

Post here if you don't find any other place for your post. But please, stay on-topic: algorithms, programming or something related to this web site and its services.

Moderator: Board moderators

Post Reply
nejhum
New poster
Posts: 8
Joined: Sun Jun 09, 2002 9:36 pm

Provide resource for exhaustive BFS algorithm

Post by nejhum »

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.
by

S M Shahed Nejhum

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

BFS

Post by Ming Han »

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

nejhum
New poster
Posts: 8
Joined: Sun Jun 09, 2002 9:36 pm

Post by nejhum »

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?
by

S M Shahed Nejhum

Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

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

Post by Ming Han »

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.

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

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.

Betovsky
New poster
Posts: 26
Joined: Wed Jun 05, 2002 7:30 pm
Location: Portugal

Post by Betovsky »

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.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Floyd vs. BFS

Post by junjieliang »

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]

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Location: Pasadena, CA

Post by C8H10N4O2 »

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

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

DISCUSSION ON EXHAUSTIVE B.F.S.

Post by nymo »

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 :D

Post Reply

Return to “Other words”