Monday, 23 May 2016

Breadth-first search (BFS)

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbors.


Input: A graph G and a starting vertex v of G
Output: All vertices reachable from v labeled as explored.

A non-recursive implementation of breadth-first search:

Breadth-First-Search(G, v):
    for each node n in G:           
        n.distance = INFINITY       
        n.parent = NIL

    create empty queue Q     

    v.distance = 0

    while Q is not empty:       
        u = Q.dequeue()
        for each node n that is adjacent to u:
            if n.distance == INFINITY:
                n.distance = u.distance + 1
                n.parent = u

1 comment:



Related Posts Plugin for WordPress, Blogger...