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

تعریف

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

الگوریتم

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

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

۲) اگر گراف دو رأس با درجه فرد داشته باشد از یکی از آن دو رأس شروع می‌کنیم.

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

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

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

پیچیدگی‌ الگوریتم

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

پیاده‌سازی اولیه

A.c

#inlcude<iostream>
#include<vector>
#include<map>
using namespace std;
 
const int max_nodes = 100, max_edges;
 
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
	//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.secend] && 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));
		adj[y].push_back(make_pair(x, i));
	}
	trail(0);
}