fleury 算法

输入 ：欧拉图

1. 任取 v0∈V(G),令P0 = v0 ，i = 0.
2. 设 Pi = v0e0v1e1……eivi,

如果E（G） - {e1,e2……ei}中没有与vi关联的边则计算停止；否则按下述条件从E（G） -{e1，e2，……ei}中任取一条边ei+1：

（a） ei+1与vi相关联；

（b） 除非无别的边可提供，否则ei+1不应该为Gi = G-{e1，e2，……ei}中的桥。

设ei+1=（vi,vi+1）,把ei+1,vi+1加入pi得到pi+1.

1. 令i=i+1，返回2.

#include<stdio.h>
void fleury ();
int Bridge (int m, int k);
int eulertu[10000][10000] = 0;
int V,E;
int main ()
{
printf(“顶点数：”);
scanf(“%d”,&V);
printf(“边数：”);
scanf(“%d”,&E); //输入几个点，几条边
int i,j;
int m,n;
int count;
int o=1;
printf(“输入有边的俩个点:n”);
for (i = 0; i < E; i++)
{
scanf("%d %d",&m,&n);       //输入有边的俩个点 
    eulertu[m][n] = eulertu[n][m] = 1;  
}
for (i = 0; i < V; i++)         //判断是否为欧拉图 
{
    count = 0;
    for (j = 0; j < V; j++) 
    {
        if (eulertu[i][j]==1) 
            count++;
    }
    if (count%2!=0)
    {
        printf("不是欧拉图");
        o=0;
        break;
    }
    if(o==0)
        break;        
}
if(o==1)
{ 
    fleury();
    printf("end");
} 
return 0;
}

void fleury ()
{
int a[10000] ={0};
int i,j;
int k = 0;
int bridge = 1;
int t;
printf(“%d—>”,a[0]);
for (i = 0; i < E; i++)
{
for (j = 0; j < V; j++)
{
if(eulertu[a[k]][j]==1)
{
eulertu[a[k]][j] = eulertu[j][a[k]] = 0;
if(Bridge(a[k],j))
{
t = j;
eulertu[a[k]][j] = eulertu[j][a[k]] = 1;
}
else
{
k++;
a[k] = j;
printf(“%d—>”,j);
bridge = 0;
break;
}
    }
    }
    if (bridge) 
    {
        eulertu[a[k]][t] = eulertu[t][a[k]] = 0;
        k++;
        a[k] = t;
        printf("%d--->",t);
    }
    bridge = 1;
}
}

int Bridge (int m, int k)
{
int a[10000];
int i = 0;
int t = 0;
int n = 0;
int p = 0;
for(i=0;i<10000;i++)
a[i]=-1;
a[t] = m;
for (t = 0; a[t] != -1; t++ )
{
for (i = 0; i < V; i++)
{
if (eulertu[a[t]][i] == 1 && i == k)
return 0;
if (eulertu[a[t]][i] == 1)
{
            p=0;
            while(a[p]==-1)
            {
                p++;
                n++;
                a[n] = i;
            }    
        }
    }
}
return 1;
}

​