مرتب‌سازی توپولوژیک

مرتب‌سازی توپولوژیک، مرتب سازی رئوس یک گراف جهت‌دار بدون طوقه و بدون دور است به طوری که هر راس قبل از رئوسی میاید که به آنها یال خروجی داده‌است.

برای مرتب‌سازی گراف روی گراف پیمایش عمق‌اول می‌زنیم به هر راسی که رسیدیم آنرا علامت می‌زنیم.

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

سپس روی بقیه رئوسی که علامت نخورده‌اند پیمایش انجام می‌دهیم ولی وارد راس‌هایی که علامت دارند نمی‌شویم.

دست آخر رئوس داخل پشته را یکی یکی بیرون می‌آوریم و چاپ می‌کنیم.

اگر گراف دور داشته باشد، الگوریتم آنرا تشخیص می‌دهد و مرتب‌سازی را ادامه نمی‌دهد. راس $u$ اگر قبل از راس $v$ وارد پشته شود به این معنی است که یالی از $u$ به $v$ وجود ندارد، پس مشکلی وجود ندارد که راس $v$ قبل از $u$ در مرتب سازی قرار بگیرد.

پیچیدگی الگوریتم برایر الگوریتم پیمایش عمق‌اول یعنی $O(v+e)$ که $v$ برابر تعداد رئوس و $e$ تعداد یال‌هاست.

توضیحات مربوط به الگوریتم $Kahn$ را می‌توانید در بخش تست غیردوری بودن گراف جهت‌دار ببنید.

topological_sort.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int N=1000; // حداکثر تعداد رئوس
int n, m; // تعداد رئوس و تعداد یال‌های جهت دار
vector<int> g[N]; // برای هر راس یک پشته که شامل راس‌هایی که به آنها یال خروجی دارد
bool used[N]; 
bool end[N]; 
vector<int> ans;
 
bool dfs (int v) {
	used[v] = true;
	for (int i=0; i<g[v].size(); ++i) {
		int to = g[v][i];
		if (!used[to])
			dfs (to);
		if(used[to]==true && end[to]==false)
			return false;
	}
	ans.push_back (v);
	end[v] = true;
	return true;
}
 
bool topological_sort() {
	fill_n(used,n,false);
	fill_n(end,n,false);
 
	ans.clear();
	for (int i=0; i<n; ++i)
		if (!used[i] && 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-1 از ورودی یکی کم می‌کنیم چون بازه‌ی معتبر ما از صفر تا
	}
	if (topological_sort())
		for(int i=n-1; i>=0; i--)
			cout << ans[i]+1 <<endl; // است n-1 به خروجی یکی اضافه می‌کنیم چون بازه‌ی معتبر ما از صفر تا
	else
		cout << "Fail!";
}

• مرتب‌سازی توپولوژیک - سایت ماکزیمال
• مرتب‌سازی توپولوژیک - ویکی‌پدیا