#header-inner {background-position: right !important; width: 100% !important;}

9/24/12

Breadth-first search (BFS)

BFS is one of simplest algorithms for searching graphs.

It is an uninformed search method that exhaustively searches the entire graph without considering the goal until it finds it.

Pseudocode:

Input: A graph G and a source (root) v of G

1  procedure BFS(G,v):
2      create a queue Q
3      enqueue v onto Q
4      mark v
5      while Q is not empty:
6          t ← Q.dequeue()
7          if t is what we are looking for:
8              return t
9          for all edges e in G.adjacentEdges(t) do
10             o ← G.opposite(t,e)
11             if o is not marked:
12                  mark o
13                  enqueue o onto Q


Space complexity

When the number of nodes (vertices) in the graph is known ahead of time, and additional data structures are used to determine which nodes have already been added to the queue, the space complexity can be expressed as O(|V|) where |V| is the cardinality of the set of nodes.

Time complexity

The time complexity can be expressed as O(|E|+|V|) since every vertex and every edge will be explored in the worst case. Note: O(|E|+|V|) may vary between O(|V|) and , O(|V|^2+|V|) depending on the number of graph edges.

BFS Tree

Above algorithm can produce BFS Tree, if marking node o (in line 12) is accompanied by setting node t as parent of node o. Such tree allows to find shortest path from any node in graph to source.

No comments:

Post a Comment