Searching

Breadth-First Search

Breadth-First Search (BFS) is also known as a level order traversal for trees. BFS works in O(V+E) similar to a DFS algorithm. However, BFS uses a queue instead of the stack. DFS dives into the graph, whereas BFS traverses the graph breadthwise.

The BFS algorithm utilizes a queue to keep track of the vertices. Unvisited adjacent vertices are visited, marked, and queued. If the vertex doesn't have any adjacent vertice, then a vertice is removed from the queue and explored.

BFS is commonly used in peer-to-peer networks, shortest path of an unweighted graph, and to find the minimum spanning tree.

BFS (G, s)      // Where G is the graph and s is the source node
      let Q be queue.
      Q.enqueue( s ) // Inserting s in queue until all its neighbour vertices are marked.
      mark s as visited.
      while ( Q is not empty)
           // Removing that vertex from queue,whose neighbour will be visited now
           v  =  Q.dequeue( )

          // processing all the neighbours of v  
          for all neighbours w of v in Graph G
               if w is not visited 
                     Q.enqueue( w ) // Stores w in Q to further visit its neighbour
                     mark w as visited.

Depth First Search

Depth First Search (DFS) is one of the first graph algorithms taught to students. DFS is an efficient algorithm used to traverse or search a graph. It can also be modified to be used in tree traversal.

The DFS traversal can start from any arbitrary node, and it dives into each adjacent vertex. The algorithm backtracks when there is no unvisited vertex, or there's a dead-end. DFS is typically implemented with a stack and a boolean array to keep track of the visited nodes. DFS is simple to implement and exceptionally efficient; it works(V+E), where V is the number of vertices and E is the number of edges.

Typical applications of the DFS traversal include topological sort, detecting cycles in a graph, pathfinding, and finding strongly connected components.

DFS-iterative (G, s):    //Where G is graph and s is source vertex
    let S be stack
    S.push( s )            //Inserting s in stack 
    mark s as visited.
    while ( S is not empty):
        //Pop a vertex from stack to visit next
        v  =  S.top( )
        S.pop( )
        //Push all the neighbours of v in stack that are not visited   
        for all neighbours w of v in Graph G:
            if w is not visited :
                S.push( w )         
                mark w as visited

DFS-recursive(G, s):
    mark s as visited
    for all neighbours w of s in Graph G:
        if w is not visited:
            DFS-recursive(G, w)

PreviousGraphs NextMinimum Spanning Tree

Last updated 1 year ago

BFS (G, s) // Where G is the graph and s is the source node let Q be queue. Q.enqueue( s ) // Inserting s in queue until all its neighbour vertices are marked. mark s as visited. while ( Q is not empty) // Removing that vertex from queue,whose neighbour will be visited now v = Q.dequeue( ) // processing all the neighbours of v for all neighbours w of v in Graph G if w is not visited Q.enqueue( w ) // Stores w in Q to further visit its neighbour mark w as visited.

DFS-iterative (G, s): //Where G is graph and s is source vertex let S be stack S.push( s ) //Inserting s in stack mark s as visited. while ( S is not empty): //Pop a vertex from stack to visit next v = S.top( ) S.pop( ) //Push all the neighbours of v in stack that are not visited for all neighbours w of v in Graph G: if w is not visited : S.push( w ) mark w as visited