> For the complete documentation index, see [llms.txt](https://dailyjournal.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://dailyjournal.gitbook.io/notes/data-structures-and-algorithms/algorithms/graphs/searching.md). # 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. ``` {% embed url="" %} ### 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. {% embed url="" %} 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="" %}