Go to Google Home
A data-code-compute resource for research and education in information visualization
InfoVis Home Learning Modules Software Databases Compute Resources References

Software > Random Breadth First Search Algorithm

Description | Pros and Cons | Applications | Details | Usage Hints | References | Acknowledgments


Search in a graph is defined as finding a path from a start node to a destination node. The cost of a search is the number of edges traversed in locating the destination node (i.e., the number of "messages" sent in the network during the search process).

Random Breadth First Search (BFS) is an uninformed search algorithm that has been proposed as an alternative to basic uninformed "flooding" [1, 2, 3]. It utilizes only local connectivity knowledge of the graph during search. Basic BFS begins at the source node by checking each neighbor if it is the destination node. If this fails, each of these neighbors check their neighbors and this continues until destination node is found. Random Random Breadth First Search improves upon basic BFS by reducing the number of messages passed during search. It randomly eliminates a fraction p of neighbors that are checked for each node. Search then proceeds from the start node checking only n neighboring nodes and proceeding forward. If at any time during the search a node N contacts a "dead-end" node (a leaf in the graph), the search process backtracks to N and continues.

Pros & Cons

Applicable to network graphs only. Random Breadth First Search Algorithm can be used to perform search on any of the structured (e.g. CAN, Chord), unstructured (e.g. PRU, Hypergrid) or random network models.


This algorithm can be used to perform search on any network graph (structured or unstructured). The search cost can be useful in comparing search performance among structured and unstructured P2P networks and also across different topologies. It can also be used to study its performance against other widely-known search algorithms like Basic Breadth First Search (BFS), Depth First Search (DFS) or Random Walk [4].


Pseudo Code of the algorithm is as follows:

define randomBFS(Graph g, float prob, Node startNode, Node destinationNode)
    Node n := startNode
    Queue q := {}
    Stack s := {}
    Enqueue(q, startNode)
     visited[startNode] := true
     while( n not equals destinationNode)
          if (queue empty)
               tempNode := pop(s)
               for each node (g)
                     visited[node] := false
          n := Dequeue(q)
          if (n not equals destinationNode)
               push(s, n)
               for each neighbor of n
                     if (visited[neighbor] = false)
                           if ( prob < rand() )
                                 visited[neighbor] := true
                                 Enqueue(q, neighbor)

Usage Hints

In the IVC Software Framework, simply select a network data model and use Analysis > Search > Breadth First Search to analyze it.



This package was developed by George Fletcher and Hardik Sheth. Hardik Sheth integrated the code into the IVC Software Framework.

Information Visualization Cyberinfrastructure @ SLIS, Indiana University
Last Modified July 10th, 2004