DFS
DFS
Depth-First Search (DFS) is a graph traversal algorithm that explores as deep as possible along each branch before backtracking. It relies on a LIFO Stack (or call stack recursion) to navigate vertices. DFS is essential for topological sorting, detecting cycles, and solving maze puzzles.
Complexity Profile
| Case | Complexity |
|---|---|
| Best Case | O(V + E) |
| Average Case | O(V + E) |
| Worst Case | O(V + E) |
| Space Complexity | O(V) |
Code Implementation
def depth_first_search(graph, node, visited=None):
if visited is None:
visited = set()
if node in visited:
return
visited.add(node)
print("Visited node:", node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
depth_first_search(graph, neighbor, visited)Real-World Applications
- Topological sorting in compiler dependencies.
- Detecting cycles in directed/undirected graphs.
- Solving mazes, puzzles, and back-tracking constraint problems.
Binary Search
Binary search is an efficient search algorithm that works on pre-sorted arrays. It repeatedly splits the search interval in half. If the target value is less than the middle element, it narrows the interval to the lower half; otherwise, it limits it to the upper half, repeating the split until the value is found or the interval is empty.
Linear Search
Linear search is the simplest search algorithm. It scans elements of a sequence sequentially, one by one, checking whether the target element matches the current element. This is useful for unsorted arrays or when data is simple and unsorted, though highly inefficient for larger arrays.