الگوریتم فلوری برای گراف‌های جهت‌دار

طبق تعریف تور اویلری، گراف G بدون جهت با درجات ورودی و خروجی برابر در هر رأس داده شده است. حال الگوریتم فلوری را برای یافتن تور اویلری در آن معرفی می‌کنیم.

در گراف جهت G داده شده، جهت پیدا کردن تور اویلری طبق الگوریتم فلوری به این صورت عمل می‌کنیم که؛

۱) اگر گراف رأس با درجه ورودی و خروجی متفاوت نداشته باشد از رأسی دلخواه شروع می‌کنیم.

۲) اگر گراف دو رأس با درجه ورودی و خروجی با یک واحد تفاوت داشته باشد از رأسی که یال خروجی بیشتر دارد شروع می‌کنیم.

۳) سایر گراف‌ها تور اویلری ندارند.

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

با توجه به زوجیت درجات رئوس اثبات می‌شود که با غیر قابل گسترش شدن گذر، یال پیمایش نشده‌ای وجود نخواهد داشت. بنابراین گذر پیمایش شده تور اویلری مورد نظر خواهد بود. اگر گراف داده شده از نوع ۱ باشد تور پیمایش شده دور اویلری خواهد بود و در حالت ۲ تور پیمایش شده یک مسیر اویلریست.

۱- رأس ابتدایی را با توجه به امکان وجود حداکثر دو رأس با درجات ورودی و خروجی متفاوت در گراف انتخاب می‌کنیم.

۲- در گراف باقی‌مانده یال‌های برشی را می‌یابیم.

۳- از میان یال‌ههای باقی‌مانده خروجی رأس کنونی، در صورت وجود یالی را انتخاب می‌کنیم که برشی نباشد. در غیر این صورت یک یال باقی‌مانده دیگر را انتخاب می‌کنیم و از یال انتخابی گذر می‌کنیم و آن را از گراف حذف می‌کنیم و به قدم دوم می‌رویم.

در پیمایش گذر مربوطه هر یال دقیقا یک بار مورد بررسی قرار می‌گیرد که در نتیجه پیچیدگی آن از (O(E می‌باشد. از طرفی در هر مرحله از پیمایش نیاز به یافتن یال‌های برشی داریم که با استفاده از الگوریتم تارجان به پیچیدگی$O(E^2)$ می‌رسیم.

A.c

#inlcude<iostream>
#include<vector>
using namespace std;
 
const int max_nodes = 100, max_edges = 100 * 100;
 
vector<pair<int, int> > adj[max_nodes];
 
bool cut[max_edges], seen[max_edges];
 
void mark_cut_edges(){
	//set the cut of the cut edges true and others false, not considering the directions
	//cut edges should be determined on the graph of edges which haven't been seen yet
}
 
void trail(int node){
	mark_cut_edges();
	bool could_exit = false;
	for(int i = 0; i < adj[node].length(); i++){
		int edge = adj[node][i];
		if(!seen[edge.second] && cut[edge.second]){
			cout<<edge.second<<endl;//output the number of the edge
			seen[edge.second] = true;
			trail(edge.first);
			could_exit = true;
			break;
		}
	}
	if(!could_exit){//could not find any non-cut edge
		for(int i = 0; i < adj[node].length(); i++){
			int edge = adj[node][i];
			if(!seen[edge.secend]){
				cout<<edge.second<<endl;//output the number of the edge
				seen[edge.second] = true;
				trail(edge.first);
				could_exit = true;
				break;
			}
		}
	}
}
 
int main(){
	int n, m;
	cin>> n>> m;
	for(int i = 0; i < m; i++){
		int x, y;
		cin>> x>> y;
		x--; y--;
		adj[x].push_back(make_pair(y, i));
	}
	trail(0);
}

نمونه مسأله در کدفورسز

• https://en.wikipedia.org/wiki/Eulerian_path