بررسی غیردوری بودن گراف جهت‌دار

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

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

پیچیدگی الگوریتم برابر الگوریتم پیمایش عمق اول است: $O(m+n)$

الگوریتم کان ($Kahn$) ابتدا تمام راس‌هایی که یال ورودی ندارند را در یک مجموعه می‌ریزد. سپس یک راس دلخواه از این مجموعه را بر می‌دارد و آنرا از گراف حذف می‌کند(یعنی یال‌های خروجی‌اش را نیز پاک می‌کند و از مجموعه مذکور هم حذف می‌شود) و سپس مجموعه را به روز رسانی می‌کند( یعنی راس‌های جدیدی که یال ورودی ندارند را در این مجموعه می‌ریزد). حال این‌کار برای راس دیگر این مجموعه تکرار می‌کند. تنها در زمانی که یک بار تمام راس‌ها وارد مجموعه شوند، می‌توان نتیجه گرفت که گراف جهت‌دار ما غیر مدور(بدون دور است). در ضمن راس‌هایی که از «مجموعه‌ی راس های بدون یال ورودی» خارج می‌کنیم، اگر به ترتیب آنها را یادداشت کنیم، یک مرتب‌سازی توپولوژیک خواهیم داشت.

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

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

هر راس یک بار داخل مجموعه و یک بار از مجموعه خارج می‌شود و به ازای هر یال حداکثر یک بار عملیات به روز رسانی انجام می‌شود پس پیچیدگی الگوریتم مانند الگوریتم عمق‌اول می‌شود: $O(m+n)$

Cycle_test.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=1000; // حداکثر تعداد رئوس
int n, m; // تعداد راس‌ها و یالها که از ورودی می‌خوانیم
vector<int> g[N]; // پشته نگه‌دارنده گراف
bool Sflag[N]; // بررسی ورود به هر راس
bool Eflag[N]; // بررسی خروج به هر راس
 
bool dfs (int v) {
	Sflag[v]=true;
	for(int i=0; i<g[v].size(); i++){
		if(Sflag[g[v][i]] && !Eflag[g[v][i]])
			return false;
		if(!Sflag[g[v][i]])
			if(!dfs(g[v][i]))
				return false;
	}
	Eflag[v]=true;
	return true;
}
bool test_graph(){
	fill_n(Sflag,n,false);
	fill_n(Eflag,n,false);
	for(int i=0; i<n;i++)
		if(!Sflag[i])
			if(dfs(i)==false)
				return false;
 
	return true;	
}
 
int main() {
	cin >> n>>m;
	for(int i=0; i<m; i++){
		int t,r;
		cin >>t>>r; 
		g[--t].push_back(--r);
                /* 
                * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                */
	}
	if(test_graph()==true)
		cout << "No Cycle"<<endl;
	else
		cout << "There is a Cycle"<<endl;
 
}

Kahn.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=1000; // حداکثر تعداد رئوس
int in_vectors[N]; // (تعداد یال ورودی هر راس (از بین رئوسی که هنوز حذف نشده‌اند
int top_sort[N]; // آرایه‌ای مرتب‌سازی توپولوژیک را نگه می‌دارد
int n, m; // تعداد رئوس و تعداد یال‌ها
vector<int> g[N]; // مجموعه‌ یال‌های گراف
vector<int> mySet; // مجموعه‌ای از راس‌ها که یال ورودی ندارند
bool test_graph() {
	for(int i=0; i<n; i++)
		if(in_vectors[i]==0)
			mySet.push_back(i);
	for(int i=0; i<n; i++){
		if(mySet.size()==0)
			return false;
		mySet.pop_back();
		int v=*mySet.end();
		top_sort[i]=v; // این آرایه در نهایت اگر دوری وجود نداشته باشد یک مرتب‌سازی توپولوزیک نگه می‌دارد
		for(int j=0; j<g[v].size(); j++){
			int to=g[v][j];
			in_vectors[to]--;
			if(in_vectors[to]==0)
				mySet.push_back(to);
		}
	}
	return true;
}
 
int main() {
	cin >> n>>m;
	vector <int> a;
	fill_n(in_vectors,n,0);
	for(int i=0; i<m; i++){
		int t,r;
		cin >>t>>r;
		g[--t].push_back(--r);
                /* 
                * است n است ولی بازه معتبر راس ها در ورودی ۱ تا n-۱ بازه معتبر راس ها برای ما صفر تا 
                * پس ما باید قبل از ذخیره یکی از آنها کم کنیم
                */
		in_vectors[r]++;
	}
	if(test_graph()==true)
		cout << "No Cycle"<<endl;
	else
		cout << "There is a Cycle"<<endl;
 
}

• گراف جهت‌دار غیر مدور - ویکی‌پدیا