Graphs Overview
MediumNodes and edges, and the four variations
Problem
Learn graphs: nodes connected by edges (directed/undirected, weighted/unweighted) and how DFS/BFS explore them.
Dots joined by lines; DFS and BFS are two ways to walk them.
The idea
A graph is nodes joined by edges, and the four axes that matter are directed or undirected, weighted or unweighted, cyclic or acyclic, connected or not. Those choices decide which algorithm applies far more than the problem's wording does.
The trick
- Unweighted shortest path is BFS; weighted needs Dijkstra or Bellman-Ford.
- Trees are just connected acyclic graphs with V-1 edges.
- Always ask whether the graph can be disconnected — it changes the driver loop.
1
1
0
1
1
0
0
0
0
0
1
1
Step 1 of 8. Scan for land (1). Each new blob is one island — DFS sinks its whole region.
1/8
Optimal
timeO(rows·cols)spaceO(rows·cols)
Depth-first sink.
1function sink(r, c) {2 if (oob(r,c) || grid[r][c] !== '1') return;3 grid[r][c] = '0';4 sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);5}Input
- grid
- 3 × 4
Memory
- at
- —
- cells marked
- 0
Output
- islands
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- edges [[0,1],[1,2]]
- Output:
- path 0-1-2
Finished the walkthrough? Add it to your streak.