首页 > 代码库 > 简单的Fleury算法模板
简单的Fleury算法模板
假设数据输入时采用如下的格式进行输入：首先输入顶点个数n和边数m，然后输入每条边，每条边的数据占一行，格式为：u，v，表示从顶点u到顶点v的一条有向边
这里把欧拉回路的路径输出了出来：
手写栈：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 #define N 1005 6 int first[N],k,degree[N],visit[N]; 7 struct stack{ 8 int top,node[N]; 9 }s;10 struct Path{11 int y,next,flag;12 }path[N<<1];13 void add(int x,int y)14 {15 path[k].y=y,path[k].next=first[x],path[k].flag=k;16 first[x]=k;17 k++;18 path[k].y=x,path[k].next=first[y],path[k].flag=k-1;19 first[y]=k;20 k++;21 }22 void dfs(int u)23 {24 s.node[++s.top]=u;25 for(int i=first[u];i!=-1;i=path[i].next){26 if(!visit[path[i].flag]){27 visit[path[i].flag]=1;28 dfs(path[i].y);29 break;30 }31 }32 }33 void Fleury(int x)34 {35 int b;36 s.top=0;37 s.node[s.top]=x;38 while(s.top>=0){39 b=0;40 int u=s.node[s.top];41 for(int i=first[u];i!=-1;i=path[i].next){42 if(!visit[path[i].flag]){43 b=1;44 break;45 }46 }47 if(b==0){//如果没有点可以扩展48 printf("%d ",s.node[s.top]);49 s.top--;50 }51 else{52 s.top--;53 dfs(s.node[s.top+1]);54 }55 }56 }57 int main()58 {59 int n,m,u,v;60 scanf("%d%d",&n,&m);61 k=0;62 memset(first,-1,sizeof(first));63 memset(degree,0,sizeof(degree));64 memset(visit,0,sizeof(visit));65 for(int i=0;i<m;i++){66 scanf("%d%d",&u,&v);67 add(u,v);68 degree[u]++,degree[v]++;69 }70 int odd=0,st=1;71 for(int i=1;i<=n;i++){72 if(degree[i]&1) odd++,st=i;73 }74 if(odd==0||odd==2) {Fleury(st);}75 else printf("No Euler path\n");76 return 0;77 }
stl容器栈：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <stack> 5 using namespace std; 6 #define N 1005 7 int first[N],k,degree[N],visit[N]; 8 stack<int> s; 9 struct Path{10 int y,next,flag;11 }path[N<<1];12 void add(int x,int y)13 {14 path[k].y=y,path[k].next=first[x],path[k].flag=k;15 first[x]=k;16 k++;17 path[k].y=x,path[k].next=first[y],path[k].flag=k-1;18 first[y]=k;19 k++;20 }21 void dfs(int u)22 {23 s.push(u);24 for(int i=first[u];i!=-1;i=path[i].next){25 if(!visit[path[i].flag]){26 visit[path[i].flag]=1;27 dfs(path[i].y);28 break;29 }30 }31 }32 void Fleury(int x)33 {34 int b;35 s.push(x);36 while(!s.empty()){37 b=0;38 int u=s.top();39 for(int i=first[u];i!=-1;i=path[i].next){40 if(!visit[path[i].flag]){41 b=1;42 break;43 }44 }45 if(b==0){//如果没有点可以扩展46 printf("%d ",s.top());47 s.pop();48 }49 else{50 s.pop();51 dfs(u);52 }53 }54 }55 int main()56 {57 int n,m,u,v;58 scanf("%d%d",&n,&m);59 k=0;60 memset(first,-1,sizeof(first));61 memset(degree,0,sizeof(degree));62 memset(visit,0,sizeof(visit));63 for(int i=0;i<m;i++){64 scanf("%d%d",&u,&v);65 add(u,v);66 degree[u]++,degree[v]++;67 }68 int odd=0,st=1;69 for(int i=1;i<=n;i++){70 if(degree[i]&1) odd++,st=i;71 }72 if(odd==0||odd==2) {Fleury(st);}73 else printf("No Euler path\n");74 return 0;75 }
输入：
9 14
1 2
1 8
2 3
2 8
2 9
3 4
4 5
4 6
4 9
5 6
6 7
6 9
7 8
8 9
结果：
1 2 3 4 5 6 4 9 2 8 7 6 9 8 1
简单的Fleury算法模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。