Royal Amethyst

Breadth First Search (BFS)

Theory: BFS is a fundamental graph traversal algorithm that explores all nodes at the current depth before moving to the next level. It uses a **First-In-First-Out (FIFO) Queue**.

Complexity: O(V + E) time, O(V) space.

Key Traits:

• Guarantees the **shortest path** in unweighted graphs.
• Optimal for finding coordinates closest to source.
• High memory usage for large graphs.

Depth First Search (DFS)

Theory: DFS explores as far as possible along each branch before backtracking. It utilizes a **Last-In-First-Out (LIFO) Stack** or Recursion.

Complexity: O(V + E) time, O(h) space (where h is height).

Key Traits:

• Excellent for topological sorting and cycle detection.
• Does **not** guarantee the shortest path.
• Very memory efficient in deep, sparse graphs.

Depth Limited Search (DLS)

Theory: DLS is a variation of DFS with a predefined maximum depth limit. It solves the infinite path problem in state-space graphs.

Complexity: O(b^L) time, O(bL) space (b=branching factor, L=limit).

Key Traits:

• Prevents searching infinite branches.
• Can be incomplete if the goal is beyond the limit.
• The foundation for **Iterative Deepening DFS**.

Dijkstra's Algorithm

Theory: Developed by Edsger Dijkstra, this "Greedy" algorithm solves the single-source shortest path problem for non-negative edge weights using a **Priority Queue (Heap)**.

Complexity: O((V + E) log V).

Key Traits:

• **Guarantees** the absolute cheapest path in weighted graphs.
• Uses "Relaxation" to continuously update node costs.
• Universal standard for GPS navigation systems.