Depth First & Breadth First Graph Search - DFS & BFS Graph Searching Algorithms

Try Our Full Platform: https://nas.io/backtobackswe 📹 Intuitive Video Explanations ❓New Unseen Questions 🔎 Get All Solutions DFS and BFS are not just graph search algorithms. They are a fundamental method for searching relationships in a certain way and visiting nodes of any sort in a desired order. These relationships may be represented in a graph, or we may be checking the distance one string is in character changes from another string, OR we may be traversing a tree a certain way. These are searching concepts, not just graph concepts. Implementation DFS can be done iteratively using a stack or done recursively because the call stack will serve as the stack to remember points to backtrack to. A stack structure can replace our stack frames from recursion, this is why DFS can be written recursively, due to the Last-In-First-Out (LIFO) of the order nodes are processed. BFS is done iteratively. It uses a queue that has a First-In-First-Out processing order. Use Cases DFS is good for things like backtracking, getting to leaf nodes in a tree, or anything where we want to prioritize going very deep into a path and exhausting possibilities before coming back. BFS is better for things like finding if a path exists between one node to another since it prioritizes width of search over depth (hence "breadth-first") and finding distance or "levels" something is away from something else. The Method 1.) Choose the data structure based on the search. 2.) Add the start node. 3.) Remove the a node from the data structure. 4.) If the node has not been seen 4a.) Mark it as seen in the "seen" set. 4b.) Do work on the node. 5.) For each of the children 5a.) If child has not been seen (not bee processed) 5ai.) Add the child to the data structure. Repeat while the data structure is not empty. Time Complexities If relationships are represented with an adjacency list then: Time: O(V + E) Space: O(V)* Where V is the total number of vertices (or n