# Searching

### Breadth-First Search <a href="#breadth-first-search" id="breadth-first-search"></a>

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.
```

{% embed url="https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/" %}

### Depth First Search <a href="#depth-first-search" id="depth-first-search"></a>

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.

{% embed url="https://static1.makeuseofimages.com/wordpress/wp-content/uploads/2021/08/dfs-graph.jpg?q=50&fit=crop&dpr=1.5" %}

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)
```

{% embed url="https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/visualize/" %}
