Connected Components نشان میدهد یک گراف بدونجهت از چند گروه مستقل تشکیل شده است. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Connected Components زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
از هر رأس دیدهنشده یک BFS یا DFS جدید شروع میکنیم؛ هر پیمایش یک component میسازد.
مراحل اجرا
- همه رأسها را unvisited میگیریم.
- از اولین رأس دیدهنشده BFS/DFS اجرا میکنیم.
- رأسهای رسیدهشده یک component هستند.
- برای رأس بعدی دیدهنشده تکرار میکنیم.
نمونه کد JavaScript
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;
}مثالهای واقعی و دنیای کار
- گروههای مستقل شبکه اجتماعی
- Island Detection
- گروه دستگاههای شبکه
- خوشههای ارتباطی کاربران
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
تقسیم گراف بدونجهت به گروههای مستقل
چه زمانی مناسب نیست؟
برای گراف جهتدار SCC مفهوم مناسبتری است.
جمعبندی
Connected Components را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.