Category : Science and Education
Archive   : PCB.ZIP
Filename : BFS

 
Output of file : BFS contained in archive : PCB.ZIP
BFS Algorithm (* breadth-first search *)
(* Search a graph or state space, depending on the problem definition. *)
(* S is the start node, T is the goal node. *)
(* Open is an ordered list of nodes (ordered by arrival time; nodes enter
at the tail and leave at the head), also called a queue. Closed is a set
of nodes (order doesn't matter). In general, nodes that need to be
searched are put on Open. As they are searched, they are removed from
Open and put in Closed. *)
(* Pred is defined for each node, and is a list of "came from" indications,
so when we finally reach T, we traverse Pred to construct a path to S. *)
1 Open <- {S} (* a list of one element *)
Closed <- {} (* the empty set *)
Pred[S] <- NULL, found <- FALSE
WHILE Open <> {} and not found DO
5 x <- the first node on Open
Open <- Open - {x} (* remove x from Open *)
Closed <- Closed + {x} (* put x in Closed *)
IF x = T THEN found <- TRUE (* we're done *)
ELSE (* continue search through node x *)
10 let R be the set of neighboring nodes of x
FOR each y in R DO
IF y is not on Open or in Closed THEN
Pred[y] <- x (* remember where we came from *)
Open <- Open + {y} (* put y on Open (at the tail) *)
15 IF found THEN
use Pred[T] to find Pred[Pred[T]] and so on until S is reached
(* this traces out the solution path in reverse *)
ELSE T cannot be reached from S


  3 Responses to “Category : Science and Education
Archive   : PCB.ZIP
Filename : BFS

  1. Very nice! Thank you for this wonderful archive. I wonder why I found it only now. Long live the BBS file archives!

  2. This is so awesome! 😀 I’d be cool if you could download an entire archive of this at once, though.

  3. But one thing that puzzles me is the “mtswslnkmcjklsdlsbdmMICROSOFT” string. There is an article about it here. It is definitely worth a read: http://www.os2museum.com/wp/mtswslnk/