Layered Breadth First Search 

RISC-Linz logo

Author: Bogdan Matasaru


Implement a layered breadth first search algorithm for a network of N nodes. The underlying graph G=(V,E) is a connected undirected graph and there is a distinguished source node i0. The problem is to find a breadth first spanning tree rooted in the node i0.


The algorithm works as follows:


  1. The information send from the k layer nodes up to the source can be positive/negative acknowledgement if there were/were not new children discovered.
  2. When a node has received negative acknowledgements from all the children or neighbors it knows that the subtree rooted in it was constructed, so it can send back negative acknowledgements to subsequent newphase messages received.


You should see a button labelled "Press Me" embedded below. If you do not see this button but the string "Please enable Java!" instead, you must enable Java on your Web browser and then reload the page.

Please enable Java!

Source Code

Maintained by: Wolfgang Schreiner
Last Modification: January 11, 1999

[Up] [RISC-Linz] [University] [Search]