Graphs tutorial
BFS and DFSWorld 6 tutorial0:00 / 0:00
Nodes and edges: explore outward from a start with a queue (breadth first) or a stack (depth first), stamping each node so you never loop.
▼Transcript
Graphs. Stations joined by lines: nodes and edges.
The move: explore from a start. Breadth first search uses a queue and ripples out, ring by ring. Depth first search uses a stack, or recursion, and dives deep first. Stamp each node visited, so you never loop.
The clue: a problem says connected, neighbours, islands, network, path, prerequisites, or fewest steps. A grid is a graph too: each cell's neighbours are up, down, left and right.
The cost: each node and edge is handled once: O of V plus E time, and O of V space for the visited set. Now let's use it on Number of Islands.