مؤلفه‌های همبند
گره‌های گراف بی‌جهت را بر اساس اینکه به هم راه دارند گروه‌بندی می‌کند: از هر گره‌ی برچسب‌نخورده یک پیمایش تازه شروع می‌شود.
در گراف بی‌جهت، مؤلفه‌ی همبند بزرگ‌ترین گروهی از گره‌هاست که همه به هم راه دارند. برای پیدا کردن همه‌ی مؤلفه‌ها:
ادامه‌ی توضیح ↓- زمان:
O(V + E) - حافظه:
O(V) - هوروویتز–ساهنی، فصل ۶
- CLRS، فصل ۱۹
سه مؤلفه: یک مثلث، یک زنجیر سه‌گره‌ای و یک جفت.
def components(graph, src):comp = {v: 0 for v in graph}count = 0for s in graph:if comp[s] == 0:count = count + 1comp[s] = countstack = [s]while stack:u = stack.pop()for v, _ in graph[u]:if comp[v] == 0:comp[v] = countstack.append(v)return comp
شروع اجرا
- گره‌ی جاری
(u) - درخت پیمایش (از parent)
- یالِ در حال بررسی
پشته stack
خالی
متغیرهای محلی
src'A'
نارنجی = در همین گام عوض شد
graph dict
- 'A': [('B', 1), ('C', 1)]
- 'B': [('A', 1), ('C', 1)]
- 'C': [('B', 1), ('A', 1)]
- 'D': [('E', 1)]
- 'E': [('D', 1), ('F', 1)]
- 'F': [('E', 1)]
- 'G': [('H', 1)]
- 'H': [('G', 1)]
Call stack
- components()خط 1
گام ۱ از ۹۱
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- check
- visit
- ورودی فعلی (n=8)
نمایش به شکل جدول
| n | check | visit |
|---|---|---|
| 4 | 10.4 | 4 |
| 8 | 27.6 | 8 |
| 12 | 41.6 | 12 |
| 16 | 56 | 16 |
| 20 | 70.8 | 20 |
| 24 | 74.4 | 24 |
| 28 | 94.4 | 28 |
توضیح
ایده
در گراف بی‌جهت، مؤلفه‌ی همبند بزرگ‌ترین گروهی از گره‌هاست که همه به هم راه دارند. برای پیدا کردن همه‌ی مؤلفه‌ها:
- گره‌ها را به ترتیب مرور کن.
- اگر گره‌ای هنوز برچسب ندارد، شمارنده‌ی مؤلفه را زیاد کن و از آن گره یک پیمایش (اینجا DFS با پشته) شروع کن؛ هر گره‌ای که پیمایش به آن برسد همان برچسب را می‌گیرد.
هزینه
هر گره یک بار برچسب می‌خورد و هر یال حداکثر دو بار بررسی می‌شود: O(V + E).
در trace به چه چیزی نگاه کنی
- عدد کنار هر گره شماره‌ی مؤلفه‌ی آن است (۰ یعنی هنوز برچسب نخورده).
- پشته زیر تصویر است؛ با سطح جزئیات «هر دور حلقه» فقط شروع هر مؤلفه‌ی تازه را ببین.