Graphs
Represents relationships between nodes and explores them using traversal techniques like DFS or BFS.
The Approach
- Represent the graph using an adjacency list or matrix.
- For DFS: Use recursion or a stack to explore as far as possible along each branch before backtracking.
- For BFS: Use a queue to explore layer by layer, finding the shortest path in unweighted graphs.
- Use a `visited` set or array to avoid getting stuck in infinite loops in cyclic graphs.
Types of Graphs
Depth-First Search (DFS)
Good for pathfinding, cycle detection, and exploring all connected components.
Goes as deep as possible before backtracking.
A
B
C
D
E
Order:
Breadth-First Search (BFS)
Good for finding the shortest path in unweighted graphs.
Goes as deep as possible before backtracking.
A
B
C
D
E
Order:
Common Problems
Number of Islands
Graphs (DFS/BFS)
Clone Graph
Graphs (DFS/BFS)
Course Schedule
Graphs (Topological Sort)
Pacific Atlantic Water Flow
Graphs (DFS/BFS)
Graph Valid Tree
Graphs