欧拉图--膜拜大师->欧拉

哎有时候真的好迷惘....总觉得有好多事要做..... 却无从下手.....

先去洗个澡吧回来今天来撸欧拉图

1.什么是欧拉图?

通过图（无向图或有向图）中所有边一次仅且一次行遍所有顶点的通路称为欧拉通路

通过图中有所有边一次且仅一次行遍所有顶点的回路称为欧拉回路，具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。

2.下面给出关于欧拉图的各种定理也是下面用代码实现的原理

i：无向图G是欧拉图当且仅当G是连通图且没有奇度顶点

ii：无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点

iii：有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度

iv：有向图D是半欧拉图当且仅当D是单向连通的且恰有两个奇度顶点其中一个顶点的入度比出度大1 一个顶点的出度比入度大1 其余顶点的入度与出度相等

3.fleury算法是如何解决欧拉图的?-----(先去碎觉了好困今天)

任取v0∈V(G)，令P0=v0；

设Pi=v0e1v1e2…ei vi已经行遍，按下面方法从中选取ei+1：

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

（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥（所谓桥是一条删除后使连通图不再连通的边）；

（c）当（b）不能再进行时，算法停止。

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=42

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 
 5 int n,m;//无向图中顶点和边的个数
 6 int num;//用来检查欧拉图的时候是否将每个点都走过
 7 int map[1020][1020];//邻接矩阵存储图
 8 int count[1010];//我用来计算奇点设置的
 9 int vis[1010];//我在进行dfs搜索时候标记该顶点是否已经被访问过了
10 int flag;//用来检查奇点个数
11 
12 void inital()//各种 初始化
13 {
14     memset(count , 0 , sizeof(count));
15     memset(vis , 0 , sizeof(vis));
16     memset(map , 0 , sizeof(map));
17 }
18 
19 void dfs(int k)//判断该图 是否是个连通图
20 {
21     int i;
22     vis[k]=1;
23     for(i=1;i<=n;i++)
24     {
25         if( !vis[i] && map[k][i] )
26         {
27             dfs(i);
28         }
29     }
30 }    
31 
32 void decide()//就是用来判断奇点个数和上面的dfs结果的
33 {
34     for(int i=1;i<=n;i++)
35     {
36         if( count[i] %2 !=0 )
37         {
38             flag++;
39         }
40         if( vis[i] == 0 )
41         {    
42             num++;
43         }
44     }
45 }
46 
47 int main()
48 {
49     int a,b,t;
50     while(~scanf("%d",&t))
51     {
52         while(t--)
53         {
54             flag=num=0;
55             scanf("%d %d",&n,&m);
56             inital();
57             for(int i=1;i<=m;i++)
58             {
59                 scanf("%d %d",&a,&b);
60                 map[a][b]=map[b][a]=1;
61                 count[a]++;
62                 count[b]++;
63             }
64             dfs(1);
65             decide();
66             if( (flag==2||flag==0) && num==0 )
67             {
68                 printf("Yes
");
69             }
70             else
71             {
72                 printf("No
");
73             }
74         }
75     }
76 }

View Code

欧拉图--膜拜大师->欧拉

相关推荐