پیدا کردن مولفه‌های قویا همبند

هر گراف جهت‌داری را می‌توان به تعدادی مولفه‌ی قویا همبند افراز کرد، برای شناخت ویژگی قویا همبندی و مولفه‌ی قویا همبندی به صفحه‌ی گراف‌های قویا همبند مراجعه کنید. هدف ما پیدا کردن مولفه‌های همبندی با الگوریتمی با پیچیدگی زمانی مناسب است.

این الگوریتم با انجام دو بار پیمایش عمق‌اول روی گراف مولفه‌های همبندی را تشخیص می‌دهد. ابتدا روی گراف پیمایش عمق‌اول می‌زنیم. از هر راسی که خارج شدیم(کارمان با آن راس تمام شد) آنرا در یک پشته می‌ریزیم. به این ترتیب راس‌ها به ترتیب زمان خروج در پشته ریخته می‌شوند. حال این‌بار روی گراف معکوس پیمایش عمق‌اول می‌زنیم. اما این‌بار از راسی شروع می کنیم که بین راس‌هایی که هنوز دیده نشده، دیرترین زمان خروج را در پیمایش اولیه داشته‌باشد. یعنی ابتدا روی بالاترین راسی که در پشته قرار دارد، در گراف معکوس پیمایش عمق اول می‌زنیم. تمام راس‌هایی که دیده می‌شوند با این راس در یک مولفه قرار دارند. تمام این راس‌ها را از پشته حذف می‌کنیم(یا علامتی روی آنها می‌زنیم به این معنی که دیده شده‌اند). حال بین راس هایی که دیده نشده‌اند راس با دیرترین زمان خروج (بالاترین راس پشته که دیده نشده) را انتخاب می‌کنیم و با شروع از آن روی گراف معکوس پیمایش عمق‌اول می‌زنیم و این روند را تا پیدا شدن تمام مولفه‌ها ادامه می‌دهیم.

زمان خروج راس $v$ را با $f(v)$ و زمان شروع ‌آن را $s(v)$ با نشان می‌دهیم.

لم: اگر $f(v) > f(u)$، آنگاه اگر مسیری از $u$ به $v$ وجود داشته‌باشد حتما مسیری از $v$ به $u$ نیز وجود دارد.

اثبات: فرض کنید مسیری از $u$ به $v$ وجود دارد. وقتی که ما وارد $u$ می‌شویم می‌دانیم هنوز از راس $v$ خارج نشدیم چون $f(v) > f(u)$ و اگر به $v$ وارد هم نشده‌باشیم، انگاه باید $u$ جد $v$ باشد، چون از $u$ به $v$ مسیر وجود دارد. که در آن صورت $f(v) < f(u)$ می‌شود که تناقض است. پس وارد راس $v$ شدیم ولی هنوز خارج نشدیم. پس $s(v) < s(u)$ که با توجه به اینکه $f(v) > f(u)$ نتیجه می‌شود $v$ جد $u$ است. مسیری از $v$ به $u$ وجود دارد.

وقتی روی گراف معکوس پیمایش عمق‌اول می‌زنیم تمام رئوسی را می‌بینیم که به ریشه‌ پیمایش (راس شروع) در گراف اصلی مسیر دارند. پس وقتی روی راسی که بیش‌ترین زمان خروج را دارد، پیمایش می‌زنیم (در گراف معکوس) تمام راس‌هایی را می‌بینیم که به این راس مسیر دارند و طبق لم این راس‌ هم به تمام این راس‌ها مسیر دارد. پس این راس‌ها با هم یک مولفه قویا همبندی تشکیل می‌دهند. و چون بقیه راس‌هایی که در این پیمایش دیده نشده‌اند به این راس مسیر ندارند نمی‌توانند جزء این مولفه‌ی باشند. حال بین بقیه رئوس راس با بیش‌ترین زمان خروج(بالا ترین راس در پشته که دیده‌نشده) را انتخاب می‌کنیم و همین روند را تکرار می‌کنیم.

به ازای پیمایش اولیه و پیمایش روی گراف معکوس $O(m+n)$ که $m$ تعداد یال‌ها و $n$ تعداد راس‌هاست، هزینه زمانی صرف کردیم. ریختن در پشته و برداشتن از آن نیز هر کدام $O(n)$ زمان صرف می‌کند. پس در کل پیچیدگی الگوریتم $O(m+n)$ می‌شود.

در این پیاده‌سازی هر مولفه در یک خط جداگانه چاپ خواهد شد.

Kosaraju.cpp

#include <iostream>
#include <vector>
using namespace std;
int n,m; // تعداد یال‌ها m تعداد راس‌ها و n
const int N=1000; // ثابتی برای مشخص کردن سقف تعداد راس‌ها
vector <int>g[N]; // محل ذخیره یال‌ها
vector <int> bg[N]; // محل ذخیره معکوس یال‌ها
vector <int> myStack; // پشته‌ای که راس‌ها در هنگام خروج در پیمایش اول در آن می‌ریزیم
int comps; // تعداد مولفه‌ها در آخر
bool used[N]; // علامتی برای اینکه مشخص شود راسی دیده‌شده یا نه
void dfs(int a){ // پیمایش اول
	used[a]=true;
	for(int i=0; i<g[a].size(); i++)
		if(!used[g[a][i]])
			dfs(g[a][i]);
	myStack.push_back(a);
	return;
}
void back_dfs(int a){ // پیمایش دوم روی گراف معکوس
	cout << a+1<<" ";
	used[a]=true;
	for(int i=0; i<bg[a].size(); i++)
		if(!used[bg[a][i]])
			back_dfs(bg[a][i]);
}
void find_comps(){ 
	fill_n(used,n,false);
	comps=0;
	for(int i=0; i<n; i++)
		if(!used[i])
			dfs(i);
	fill_n(used,n,false);
	while(myStack.size()!=0){
		// میریزد و آنرا از پشته حذف می‌کند v دو خط بعدی بالاترین عضو پشته را در متغیر
		myStack.pop_back(); 
		int v=*(myStack.end()); 
		if(!used[v]){
			cout << ++comps<<": ";
			back_dfs(v);
			cout << endl;
		}
	}
}
 
int main(){
	cin >> n>>m;
	for(int i=0; i<m; i++){
		int a,b;
		cin >>a>>b;
		g[a-1].push_back(b-1);
		bg[b-1].push_back(a-1);
		/* است n-1 بازه‌ی معتبر راس‌ها برای برنانه صفر تا
		 * می‌باشد به همین n اما بازه‌ی معتبر ورودی یک تا
 * دلیل قبل از ذخیره یکی از ورودی‌ها کم می‌کنیم		
		 */
	}
	find_comps();
	return 0;
}

• الگوریتم کسارجو - ویکی‌پدیا