Part VI · Graph Algorithms and Tree-Graph Techniques
33. BFS, DFS and Graph Connectivity
7 lessons•32 topics•Intermediate / Advanced
7 of 7 lessons published
33.015 animated
Breadth-first search
- Queue frontier
- Visited array
- Unweighted shortest distance
- BFS parent tree
- Multi-source BFS
33.025 animated
Depth-first search
- Recursive DFS
- Iterative DFS
- Discovery/finish time
- DFS tree
- Visited colors
33.035 animated
Connected components
- Undirected components
- Component labeling
- Number of islands
- Flood fill
- Region sizes
33.044 animated
Cycle detection
- Undirected DFS parent
- Directed three-color DFS
- DSU undirected cycle detection
- Edge classification
33.054 animated
Bipartiteness
- Two-coloring
- BFS/DFS coloring
- Odd cycle obstruction
- Component-by-component checking
33.064 animated
Graph reachability
- Path existence
- Transitive closure concept
- Reverse graph reachability
- Reachability matrix
33.075 animated
Implicit graph searches
- State-space BFS
- Word ladder
- Lock puzzle
- Grid movement
- 0/1 configuration states