Graphs
Graphs are the most general data structure, capable of modeling arbitrary relationships. Traversal, pathfinding, and connectivity are the most common problem categories.
Fundamental techniques to visit every node and edge. DFS uses a stack (often implicit via recursion) to go deep, while BFS uses a queue to explore level by level.
Example Problems:
Number of IslandsClone GraphMax Area of Island
Solution Spotlight: Number of Islands (DFS)
This solution iterates through the grid. When it finds a piece of land ('1'), it increments the island count and starts a DFS traversal. The DFS recursively visits all connected land cells, marking them as visited ('0') to ensure each island is counted only once.
NumberofIslands(DFS).java
Loading code syntax...