欧拉回路与欧拉路径

佚名 6年前 (2019-05-10) 随笔 1710人围观抢沙发百度已收录

给定一个无向图G, 一条路径经过图G的每一条边, 且仅经过一次, 这条路径称为欧拉路径(Eulerian Tour), 如果欧拉路径的起始顶点和终点是同一顶点,则称为欧拉回路(Eulerian circuit).

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

欧拉路径算法：

　　无向图G存在欧拉路径的充要条件： 1.图G是连通的。

2.至多除两个点外（可以为0个，连通图不可能有且仅有一个顶点的度为奇数），其他所有顶点的度为偶数。

要找欧拉路径，满足上述条件，只要简单的找出一个度数为奇数的节点，遍历节点，看是否图连通。

判断一个图中是否存在欧拉回路：

一、无向图

每个顶点的度数都是偶数，则存在欧拉回路。

二、有向图

每个节顶点的入度都等于出度，则存在欧拉回路。

三、混合图（有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道）

找到一个给每条无向边定向的策略，使得每个顶点的入度等于出度，这样就能转换成有向图的情况。这就可以转化成一个二分图的最大匹配问题。

1.一道简单到没什么意义的题目,给出一个无向图,求是否存在欧拉回路,存在输出1,不存在输出0, 只要先判断是否为一个连通图（tarjan, dfs, bfs, 并查集都可以）, 再判断是否每个点的度数都为偶数.

http://acm.hdu.edu.cn/showproblem.php?pid=1878

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define mem(a, b) memset(a, b, sizeof(a))
 4 
 5 int n, m;
 6 int pre[1010];
 7 int deg[1010];
 8 
 9 int find(int x)
10 {
11     if(pre[x] == x)
12         return x;
13     else
14     {
15         int root = find(pre[x]);
16         pre[x] = root;
17         return pre[x];
18     }
19 }
20 
21 int main()
22 {
23     int flag;
24     while(scanf("%d", &n) != EOF)
25     {
26         if(n == 0)
27             break;
28         flag = 1;
29         mem(deg, 0);
30         for(int i = 1; i <= n; i ++)
31             pre[i] = i;   //并查集初始化 
32         scanf("%d", &m);
33         for(int i = 1; i <= m; i ++)
34         {
35             int a, b;
36             scanf("%d%d", &a, &b);
37             deg[a] ++, deg[b] ++;
38             int x = find(a), y = find(b);
39             if(x != y)
40                 pre[y] = x;
41         }
42         for(int i = 1; i < n; i ++)//判断是否是连通的 
43             if(find(i) != find(i + 1))
44             {
45                 flag = 0;
46                 break;
47             }
48         for(int i = 1; i <= n; i ++)
49         {//判断是否每个顶点的度都是偶数 
50             if(deg[i] % 2)
51             {
52                 flag = 0;
53                 break;
54             }
55         }
56         if(flag)
57             printf("1\n");
58         else
59             printf("0\n");
60     }
61     return 0;
62 }