Graph
Breadth-First Search
Breadth-First Search is an algorithm for searching graph data structures. It starts at a specified source node and explores all its immediate neighbors before moving on to the next level of neighbors.
- Time complexity is Linear, i.e. O(v + e)
- Space complexity is Linear, i.e. O(v)
- For large graphs the space complexity is described in terms of depth making it exponential, i.e. O(b^d)
Iterative Depth-First Search
An iterative depth-first search algorithm using a stack, exploring as far along each branch as possible before backtracking, useful for pathfinding and cycle detection.
Recursive Depth-First Search
A recursive depth-first search algorithm that explores branches deeply before backtracking, managing traversal state with recursion.
- Time complexity of insertion and deletion is Constant, i.e. O(1)
- Time complexity of search is is Linear, i.e. O(n)
- Space complexity is Linear, i.e. O(n)