www.pudn.com > Fleury.rar > Fleury.cpp, change:2008-06-03,size:1668b

#include "SqStack.h" 
#include "Queue.h" 
 
typedef int Graph[200][200]; 
int v,e; 
 
void DFS(Graph &G,SqStack &S,int x,int t) 
{ 
	int k=0,i,m,a; 
	Push(S,x); 
	for(i=t;i<v;i++) 
		if(G[i][x]>0) 
		{ 
			k=1; 
			G[i][x]=0; 
			G[x][i]=0; 
			DFS(G,S,i,0); 
			break; 
		} 
	if(k==0) 
	{ 
		Pop(S); 
		GetTop(S,m); 
		G[x][m]=1; 
		G[m][x]=1; 
		a=x+1; 
		if(StackLength(S)!=e) 
		{ 
			Pop(S); 
			DFS(G,S,m,a); 
		} 
		else 
			Push(S,x); 
	} 
} 
 
int BFSTest(Graph G) 
{ 
	int a[200],x,i,k=0; 
	LinkQueue Q; 
	InitQueue(Q); 
	EnQueue(Q,0); 
	for(i=0;i<v;i++) 
		a[i]=0; 
	a[0]=1; 
	while(!QueueEmpty(Q)) 
	{ 
		DeQueue(Q,x); 
		for(i=0;i<v;i++) 
			if(G[x][i]>0) 
				if(a[i]!=1) 
				{ 
					a[i]=1; 
					EnQueue(Q,i); 
				} 
	} 
	for(i=0;i<v;i++) 
		if(a[i]==0) 
		{ 
			k=1; 
			break; 
		} 
	if(k==1)  
		return 0; 
	else  
		return 1; 
 
} 
 
void Euler(Graph &G,int x)  
{ 
	int k=0,m; 
	SqStack S; 
	InitStack(S); 
	DFS(G,S,x,0); 
	cout<<"该图的一个欧拉回路为："; 
	while(!StackEmpty(S)) 
	{ 
		GetTop(S,m); 
		cout<<m+1; 
		Pop(S); 
	} 
	cout<<endl; 
} 
 
 
void main() 
{ 
	int i,j,m,n,sum,k=0; 
	Graph G; 
	cout<<"输入图的顶点数:"; 
	cin>>v; 
	cout<<"输入图边的数目:"; 
	cin>>e; 
	for(i=0;i<v;i++) 
		for(j=0;j<v;j++) 
			G[i][j]=0; 
	cout<<"输入"<<e<<"条边对应的顶点\n"; 
	for(i=0;i<e;i++) 
	{ 
		cout<<"第"<<i+1<<"条边:"; 
		cin>>m; 
		cin>>n; 
		G[m-1][n-1]=1; 
		G[n-1][m-1]=1; 
	} 
	if(BFSTest(G)==0)  
	{ 
		cout<<"该图不是连通图！\n"; 
		exit(0); 
	} 
	for(i=0;i<v;i++) 
	{ 
		sum=0; 
		for(j=0;j<v;j++) 
			sum+=G[i][j]; 
		if(sum%2==1) 
		{	k=1; 
			break; 
		} 
	} 
	if(k==1) cout<<"该图不存在欧拉回路！\n"; 
	else 
		Euler(G,0); 
 
}