The Way of C++

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  55 Posts :: 0 Stories :: 19 Comments :: 0 Trackbacks

公告

The first time i use this blog, i will write something that i learn which i think is worth write down.

常用链接

留言簿(1)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

判断一个图中是否存在欧拉回路(每条边恰好只走一次,并能回到出发点的路径),在以下三种情况中有三种不同的算法:

一、无向图
每个顶点的度数都是偶数,则存在欧拉回路。

二、有向图(所有边都是单向的)
每个节顶点的入度都等于出度,则存在欧拉回路。

以上两种情况都很好理解。其原理就是每个顶点都要能进去多少次就能出来多少次。

三、混合图(有的边是单向的,有的边是无向的。常被用于比喻城市里的交通网络,有的路是单行道,有的路是双行道。)
找到一个给每条无向的边定向的策略,使得每个顶点的入度等于出度,这样就能转换成上面第二种情况。这就可以转化成一个二部图最大匹配问题。网络模型如下:

1. 新建一个图。
2. 对于原图中每一条无向边i,在新图中建一个顶点e(i);
3. 对于原图中每一个顶点j,在新图中建一个顶点v(j)。
4. 如果在原图中,顶点j和k之间有一条无向边i,那么在新图中从e(i)出发,添加两条边,分别连向v(j)和v(k),容量都是1。
5. 在新图中,从源点向所有e(i)都连一条容量为1的边。
6. 对于原图中每一个顶点j,它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度,从而使它的入度等于总度数的一半,也就是(in + out + un) / 2(显然与此同时出度也是总度数的一半,如果总度数是偶数的话)。当然,如果in已经大于总度数的一半,或者总度数是奇数,那么欧拉回路肯定不存大。如果in小于总度数的一半,并且总度数是偶数,那么我们在新图中从v(j)到汇点连一条边,容量就是(in + out + un) / 2 – in,也就是原图中顶点j还需要多少入度。

按照这个网络模型算出一个最大流,如果每条从v(j)到汇点的边都达到满流量的话,那么欧拉回路成立。

这个算法可以用在ZJU#1992(http://acm.zju.edu.cn/show_problem.php?pid=1992


弗罗莱(Fleury)算法求欧拉回路

算法轮廓:
(1)任取v0∈V(G),令P0=v0.
(2)设Pi=v0e1v1e2…eivi已经行遍,按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1:
(a)ei+1与vi相关联;
(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的
(3)当(2)不能再进行时,算法停止。

可以证明,当算法停止时所得简单回路Pm=v0e1v1e2…emvm(vm=v0)为G中一条欧拉回路。
程序文件夹:33333

//输入一个无向图,先判断是否存在欧拉路,若有求出一条欧拉路


/先输入顶点数和边数,之后输入每条边连接的2个点


//例如


//5 6     (5个点,6条边)


//1 2


//1 3


//2 3


//2 5


//2 4


//4 5

 1#include <stdio.h>
 2#include <string.h>
 3
 4
 5struct stack
 6{int top , node[210];} f; //顶点的堆栈
 7
 8int a[201][201]; //图的邻接矩阵
 9
10int n;
11
12void dfs(int x)       //图的深度优先遍历
13{
14int i;
15
16f.top ++; f.node[f.top] = x;
17
18for (i = 1; i <= n; i ++)
19
20          if (a[i][x] > 0)
21          {
22              a[i][x] = 0; a[x][i] = 0;     //删除此边
23
24              dfs(i);
25
26              break;
27          }

28}

29
30void Euler(int x)     //欧拉路算法
31{
32int i , b;
33
34f.top = 0; f.node[f.top] = x;     //入栈
35
36while (f.top >= 0)
37{
38          b = 0;
39
40          for (i = 1; i <= n; i ++
41    if (a[f.node[f.top]][i] > 0
42    {b = 1break;}
43
44          if (b == 0)       //如果没有点可以扩展,输出并出栈
45          {
46              printf("%d " , f.node[f.top]);
47
48              f.top --;
49          }

50          else {f.top --; dfs(f.node[f.top+1]);}        //如果有,就DFS
51      }

52}

53
54int main()
55{
56
57int m , s , t , num , i , j , start;
58
59      //input
60
61      scanf("%d %d" , &n , &m); //n顶点数    m边数
62
63      memset(a , 0 , sizeof(a));
64
65      for (i = 0; i < m; i ++)
66      {
67          scanf("%d %d" , &s , &t);
68          a[s][t] = 1; a[t][s] = 1;
69      }

70
71
72      //判断是否存在欧拉回路
73
74      s = 0; start = 1;
75
76      for (i = 1; i <= n; i ++)
77      {
78          num = 0;
79
80          for (j = 1; j <= n; j ++)
81              num += a[i][j];
82
83          if (num % 2 == 1
84{start = i; s ++;}
85      }

86
87      if ((s == 0|| (s == 2)) 
88Euler(start);
89      else printf("No Euler path\n");
90
91      getchar(); getchar();
92      return 0;
93}

94

posted on 2007-12-21 19:36 koson 阅读(1159) 评论(3)  编辑 收藏 引用 所属分类: DataStruct And Algorithm

Feedback

# re: Euler Circle Problem 2008-06-04 09:47 colorain
仔细看了代码,一个Euler()和dfs()就搞定了这个程序,很厉害啊!

不过有一点不懂,就是算法中并没有判断是否是“桥”,那么是依据什么呢?

似乎很简单的操作,我就是不知道它是如何 遵循 Fleury算法啊!??
  回复  更多评论
  

# re: Euler Circle Problem 2008-06-04 09:57 colorain
另外欧拉回路问题,在网上搜索了一下,似乎没什么叫 “Euler Circle”的
很多都叫Euler circuits,其他的还有Euler trial,Euler path等  回复  更多评论
  

# re: Euler Circle Problem 2008-06-09 14:20 清水
我也是同感,怎么会不判断桥就搞定了。高!  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理