پیدا کردن مولفه های همبندی در گراف
یک گراف بدون جهت با n راس و m یال داریم و وظیفه ما پیدا کردن مولفه های همبندی این گراف است. در گراف های بدون جهت ۲ راس متعلق به یک مولفه همبندی هستند اگر و تنها اگر یک مسیر بین آن ها با استفاده از یال های این گراف باشد و هیچ مسیری هم بین دو مولفه همبندی متفاوت وجود ندارد. این مساله در گراف جهت دار را مولفه های قویا همبند می گویند که می توانید توضیح آن را در بخش بعدی بخوانید.
- برای حل کردن این مساله هم می توانیم از BFS و هم می توانیم از DFS استفاده کنیم. در واقع باید دنباله ای از DFS ها را روی گراف اجرا کرد : اولین DFS را روی یکی از رئوس گراف مانند v اجرا می کنیم و با این کار تمام رئوس متعلق به اولین مولفه همبندی پیدا خواهند شد. سپس اولین راس از رئوس باقی مانده که دیده نشده (mark[u]=false) پیدا می کنیم و روی آن هم DFS می زنیم. بدین ترتیب رئوس متعلق به دومین مولفه همبندی هم پیدا می شود و همین کار را ادامه می دهیم تا جایی که هیچ راسی که دیده نشده است، باقی نماند. اردر این الگوریتم از (O(n+m است. چون هیچ راسی دو بار دیده نمی شود و این بدین معنی است که هر یال دقیقا دو بار طی می شود (دیده می شود). یک بار از یک سر آن و بار دیگر از آن سرش.
int n;
vector<int> g[MAXN] ;
bool used[MAXN] ;
vector<int> comp ;
void dfs(int v) {
used[v] = true ;
comp.push_back(v);
for (size_t i = 0; i < (int) g[v].size(); ++i) {
int to = g[v][i];
if (!used[to])
dfs(to);
}
}
void find_comps() {
for (int i = 0; i < n ; ++i)
used [i] = false;
for (int i = 0; i < n ; ++i)
if (!used[i]) {
comp.clear();
dfs(i);
cout << "Component:" ;
for (size_t j = 0; j < comp.size(); ++j)
cout << ' ' << comp[j];
cout << endl ;
}
}
-
مهم ترین تابعی که در این کد استفاده شده است مربوط به تابع ()find_comps است که مولفه های همبندی گراف را پیدا کردیم و نمایش می دهد.
-
لیست همسایگی راس های گراف به عنوان ورودی داده شده است و [g[i شامل همسایه های راس i است.
-
MAXN مساوی حداکثر تعداد رئوس گراف است. ( معمولا MAXN را بیشتر از این حداکثر مقدار می گیرند : MAXN = n + 10 )
-
وکتور [comp[i شامل رئوسی است که در مولفه همبندی i ام وجود دارند.