Connected Components
Learn Connected Components (Graphs, Advanced DSA) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Finding Separate "Islands" in a Graph A connected component is a maximal set of vertices all reachable from each other. Finding all components: run DFS (or BFS) from any UNVISITED vertex, marking everything it reaches as one component, and repeat from the next unvisited vertex until all vertices are covered.
More lessons in Graphs
- Graph Representation - Adjacency Matrix
- Graph Representation - Adjacency List
- Directed Graph
- Undirected Graph
- Weighted Graph
- BFS
- DFS
- Cycle Detection
- Bipartite Graph
- Topological Sort
- Kahn's Algorithm
- DFS Topological Sort
- Shortest Path - BFS
- Shortest Path - Dijkstra
- Shortest Path - Bellman-Ford
- Shortest Path - Floyd-Warshall
- Minimum Spanning Tree - Prim's
- Minimum Spanning Tree - Kruskal's
- Disjoint Set Union - DSU
- Union-Find
- Strongly Connected Components - Kosaraju
- Strongly Connected Components - Tarjan
- Bridges
- Articulation Points
- Euler Path / Circuit
- Hamiltonian Path / Cycle
- Graph Coloring
- Network Flow
- Maximum Flow
- Bipartite Matching