This guide explains Connected Components from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Connected Components belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
از هر رأس دیدهنشده یک BFS یا DFS جدید شروع میکنیم؛ هر پیمایش یک component میسازد.
Step-by-step process
- همه رأسها را unvisited میگیریم.
- از اولین رأس دیدهنشده BFS/DFS اجرا میکنیم.
- رأسهای رسیدهشده یک component هستند.
- برای رأس بعدی دیدهنشده تکرار میکنیم.
JavaScript example
function components(graph) {
const seen = new Set(), result = [];
for (const start of Object.keys(graph)) {
if (seen.has(start)) continue;
const comp = [], stack = [start]; seen.add(start);
while (stack.length) {
const u = stack.pop(); comp.push(u);
for (const v of graph[u] ?? []) if (!seen.has(v)) {
seen.add(v); stack.push(v);
}
}
result.push(comp);
}
return result;
}Real-world and workplace examples
- گروههای مستقل شبکه اجتماعی
- Island Detection
- گروه دستگاههای شبکه
- خوشههای ارتباطی کاربران
Time and space complexity
O(V + E) time و O(V) space
When should you use it?
Use it when the problem matches this condition: تقسیم گراف بدونجهت به گروههای مستقل.
When is it not a good fit?
It is usually not the best choice when: برای گراف جهتدار SCC مفهوم مناسبتری است..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.