欧拉路问题-白红宇

欧拉路问题

阅读量：7166 次

发布时间：2019-06-29

本文共 3821 字，大约阅读时间需要 12 分钟。

欧拉路问题，俗称“一笔画”问题

给定一张无向图。若存在一条从节点S到节点T的路径，恰好不漏不重的经过每一条边一次（可以重复经过节点），则称该路径为S到T的欧拉路

若存在一条从节点S出发，恰好不漏不重地经过每一条边（可以重复经过图中节点）最终回到起点S，则该路径称为欧拉回路。

存在欧拉回路的无向图称为欧拉图

欧拉图判定

一张无向图为欧拉图，当且仅当无向图联通，且每个节点的度都是偶数

欧拉路存在性判定

一张无向图存在欧拉路，当且仅当无向图连通，并且图中恰好有两个节点的度数为奇数，其他节点的度数为偶数。这两个度数为奇数的节点就是起点S和终点T

欧拉回路的方案

在保证一张无向图时欧拉图时

欧拉图每个节点度数为偶数说明：只要到达一个节点，就必定存在有一条尚未走过的边可以离开该点。

故在伪代码中调用dfs(1)，不断递归，每次都走到“从x出发的第一条未访问的边”的另一端点y，最终一定能回到节点1，产生一条回路

但是这条回路不能保证经过图中的每条边。所以dfs函数会继续考虑从x出发的其他未访问的边，找到第二条回路

伪代码实际找出了若干条回路，我们需要把这些回路按照适当的方法拼接在一起，形成整张图的欧拉回路，一个拼接方法就是把第二条回路嵌入第一条回路中间

而伪代码中的栈，替我们完成了这个拼接工作，最后，把栈中的所有节点倒序输出，就得到了一条欧拉回路

上述算法的复杂度时O(NM)。因为一个点会被重复遍历多次，每次都会扫描与它相连的所有的边，虽然大部分的边已经访问过了

假设我们使用邻接表来存储无向图，我们可以在访问一条边(x, y)后，及时修改表头head[x]，令它指向下一条边。

这样我们每次只需去除head[x]，就自然跳过了所有已经访问过的边

因为欧拉回路的DFS的递归层数时O(M)级别，容易造成系统栈溢出。我们可以用另一个栈，模拟机器的递归过程把代码转为非递归实现

最后复杂度为O(N + M)

1 #include
     
       2 using namespace std; 3 const int maxn = 500010; 4 struct shiki { 5     int y, net; 6 }e[maxn << 1]; 7 int lin[maxn], len = 0; 8 int s[maxn], ans[maxn]; 9 bool vis[maxn];10 int n, m, t_f = 0, t_s = 0;11 12 inline int read() {13     int x = 0, y = 1;14     char ch = getchar();15     while(!isdigit(ch)) {16         if(ch == '-') y = -1;17         ch = getchar();18     }19     while(isdigit(ch)) {20         x = (x << 1) + (x << 3) + ch - '0';21         ch = getchar();22     }23     return x * y;24 }25 26 inline void insert(int xx, int yy) {27     e[++len].y = yy;28     e[len].net = lin[xx];29     lin[xx] = len;30 }31 32 inline void euler() {33     s[++t_f] = 1;34     while(t_f > 0) {35         int x = s[t_f], i = lin[x];36         while(i && vis[i]) i = e[i].net;37         if(i) {38             s[++t_f] = e[i].y;39             vis[i] = vis[i ^ 1] = true;40             lin[x] = e[i].net;41         }42         else t_f--, ans[++t_s] = x;43     }44 }45 46 int main() {47     n = read(), m = read();48     len = 1;49     for(register int i = 1; i <= m; ++i) {50         int x = read(), y = read();51         insert(x, y);52         insert(y, x);53     }54     euler();55     cout << "One of all Euler circuits is : "<< ' ';56     for(register int i = t_s; i >= 1; --i)57         cout << ans[i] << ' ';58     return 0;59 }

例题：Watchcow(poj2230)

给定N个点M条边的无向图(1 <= N <= 10^4, 1 <= M <= 5 * 10^4)，求一条路径，从节点1出发，最后回到节点1，并且满足每条边恰好被沿着正，反两个方向分别经过一次。

若有多种方案，输出一种即可

按照一般的存储方式，无向边会在邻接表中以正、反两个方向分别被保存一次，若没有vis标记，则按照表头数组head的更新方法，每条无向边会被正反各经过一次，恰好符合题目要求

请自己动手写递归吧！

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #include
               11 #include
                
                 12 #include
                 
                  13 using namespace std;14 const int maxn = 50010;15 struct shiki {16 int y, net;17 }e[maxn << 1];18 int lin[maxn], len = 0;19 int n, m, t_f = 0, t_s = 0;20 int s[maxn], ans[maxn << 1];21 22 inline int read() {23 int x = 0, y = 1;24 char ch = getchar();25 while(!isdigit(ch)) {26 if(ch == '-') y = -1;27 ch = getchar();28 }29 while(isdigit(ch)) {30 x = (x << 1) + (x << 3) + ch - '0';31 ch = getchar();32 }33 return x * y;34 }35 36 inline void insert(int xx, int yy) {37 e[++len].y = yy;38 e[len].net = lin[xx];39 lin[xx] = len;40 }41 42 inline void euler() {43 s[++t_f] = 1;44 while(t_f > 0) {45 int x = s[t_f], i = lin[x];46 //while(i) i = lin[i];47 if(i) {48 s[++t_f] = e[i].y;49 lin[x] = e[i].net;50 }51 else t_f--, ans[++t_s] = x;52 }53 }54 55 int main() {56 // freopen("watchcow.in", "r", stdin);57 // freopen("watchcow.out", "w", stdout); 58 n = read(), m = read();59 len = 1;60 for(register int i = 1; i <= m; ++i) {61 int x = read(), y = read();62 insert(x, y);63 insert(y, x);64 }65 euler();66 for(register int i = 1; i <= t_s; ++i)67 cout << ans[i] << '\n';68 return 0;69 }

事实证明，WA了！但是，我不觉得有锅！

转载于:https://www.cnblogs.com/ywjblog/p/9569313.html

你可能感兴趣的文章