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.



Pseudocode

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
    Q.enqueue(v)                     

    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
                Q.enqueue(n)

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...