首页 > 其他 > 详细

欧拉回路

时间:2019-02-11 19:07:55      阅读:57      评论:0      收藏:0      [点我收藏+]

标签:none   pre   then   欧拉路   hid   amp   play   strong   求解   

欧拉回路:图G经过每条边一次且仅一次的回路称为欧拉回路

欧拉路径:图G经过每条边一次且仅一次的路径称为欧拉路径

 

定理:

无向图

(1)无向图G为欧拉图,当且仅当G为连通图,且所有点的度数为偶数

(2)无向图G为半欧拉图,当且仅当G为连通图,且除了两个节点度数为奇数外,其他节点度数均为偶数

 

有向图

(1)有向图G为欧拉图,当且仅当G的基图为连通图,且所有顶点的入度与出度相同

(2)有向图G为半欧拉图,当且仅当G的基图为连通图,且存在顶点u的入度比出度大1,v的入度比出度小1,其他顶点的入度与出度相同

 

欧拉回路的求解方法:

(1)递归:

伪代码:
Euler(start);

  For顶点start的每个邻接点v

  IF边(start,v)未被标记Then{

    将边(start,v)标记;

    将边(v,start)标记;

    Euler(v);

    将(start,v)边加入栈S;

  }

void dfs(int u) //记录节点(会缺少第一个起点) 
{
    for(int &i=head[u];i;i=next[i]){
        int tp=ver[i];
        if(!vis[i]){
            vis[i]=vis[i^1]=1;
            dfs(tp);
            ans[++t]=tp;
        }
    }
}

 

(2)非递归:

技术分享图片
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100100;
int head[maxn],ver[maxn],next[maxn],vis[maxn],tot;
int sk[maxn],ans[maxn],m,n,top,t;
void add(int x,int y)
{
    ver[++tot]=y;next[tot]=head[x];head[x]=tot;
} 
void euler() //非递归写法 
{
    sk[++top]=1; //记录起始节点 
    while(top>0){
        int x=sk[top];
        int i=head[x];
        while(i&&vis[i]) i=next[i];  //找到一条未访问的路径 
        if(i){  //沿着这条路递归 
            sk[++top]=ver[i];
            head[x]=next[i];
            vis[i]=vis[i^1]=true; //双向边,所以更新两个 
        }
        else{ //模拟回溯,记录结果
            top--;
            ans[++t]=x;
        }
    }
}
int main(void)
{
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    euler();
    for(int i=t;i;i--) printf("%d ",ans[i]);
    return 0;
}
/*
6 9
1 2
2 3
3 4
4 5
5 6
6 1
1 3
3 5
1 5
*/
View Code

 

欧拉回路

标签:none   pre   then   欧拉路   hid   amp   play   strong   求解   

原文:https://www.cnblogs.com/2018zxy/p/10362863.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 designnerd.net 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号