首页 > 代码库 > 欧拉回路
欧拉回路
基本概念及定理
1. 欧拉通路、欧拉回路、欧拉图
无向图：
1) 设G是连通无向图，则称经过G的每条边一次并且仅一次的路径为欧拉通路；
2) 如果欧拉通路是回路（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；
3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。
有向图：
1) 设D是有向图，D的基图连通，则称经过D的每条边一次并且仅一次的有向路径为有向
欧拉通路；
2) 如果有向欧拉通路是有向回路，则称此有向回路为有向欧拉回路（directed Euler circuit）；
3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。
请思考图5.1中的无向图及有向图是否为欧拉图或有向欧拉图。
图5.1 欧拉回路及有向欧拉回路
2. 定理及推论
欧拉通路和欧拉回路的判定是很简单的，请看下面的定理及推论。
定理5.1 无向图G存在欧拉通路的充要条件是：
G为连通图，并且G仅有两个奇度结点（度数为奇数的顶点）或者无奇度结点。
推论5.1：
1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。
2) 当G是无奇度结点的连通图时，G必有欧拉回路。
3) G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。
EXP图5.1(a)所示的无向图，存在两个奇度顶点v2和v5，所以存在欧拉通路，且欧拉通路必
以这两个顶点为起始顶点和终止顶点；该无向图不存在欧拉回路。图5.1(b)所示的无向图为欧拉
图。
定理5.2 有向图D存在欧拉通路的充要条件是：
D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余
顶点的出度与入度都相等，而这两个顶点中一个顶点的出度与入度之差为1，另一个顶点的出度
与入度之差为-1。
推论5.2：
1) 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的
有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为
终点。
2) 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。
3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、入度
都相等。
例如图5.1(c)所示的有向图，顶点v2和v4入度和出度均为1；顶点v1的出度为2、入度为1，
二者差值为1；顶 点v3的出度为1、入度为2，二者相差为-1；所以该有向图只存在有向欧拉通路，
且必须以顶点v1为始点，以顶点v3为终点。图5.1(d)所示的有向图不存在有向欧拉通路。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 using namespace std; 5 const int MAX = 60; 6 int edge[MAX][MAX]; 7 int degree[MAX]; 8 int in[MAX],out[MAX]; 9 int n,type; //judge grape 类型 10 int e; //边数 11 int top; // 栈底 初始化为 0； 12 int stack[MAX]; //记录欧拉通路的路径 13 int vis[MAX]; //是否已经访问； 14 void DFS(int cur) //连通性的判断 是否完全访问掉 15 { 16 int i ; 17 for(i = 0; i<n; i++) 18 { 19 if(!vis[i]&&edge[cur][i]) 20 { 21 vis[i] = 1; 22 DFS(i); 23 } 24 } 25 } 26 27 28 // 判断是否存在欧拉回路: 29 // 无向图中: 连通图且所有顶点度数为偶数 30 // 有向图中: 连通图且所有顶点的入度等于出度 31 bool judge() 32 { 33 memset(vis,0,sizeof(vis)); //访问初始化 34 DFS(0); 35 for(int i =0; i<n; i++) 36 { 37 if(!vis[i]) 38 return false; 39 } //连通性的判断 是否完全访问掉 40 if(type) //有向图 41 { 42 for (int i=0; i<n; i++) 43 if (in[i] != out[i]) 44 { 45 return false; 46 } 47 } 48 else //无向图 49 { 50 for(int i =0; i<n; i++) 51 { 52 if(degree[i]%2) 53 { 54 return false; 55 } 56 } 57 } 58 return true; 59 } 60 // 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜 61 void DFS_first(int cur ,int pos) 62 { 63 int i,a,b; 64 stack[top++] = cur; 65 for(i = pos;i<n;i++) 66 { 67 if(edge[cur][i] != 0) 68 { 69 edge[cur][i] = 0; 70 out[cur]--; 71 in[i]--; 72 DFS_first(i,0); 73 break; 74 } 75 } 76 if(i==n && top<n) // 走投无路, 而且还有边的时候, 退回一步 77 { 78 b = stack[--top]; 79 a = stack[--top]; 80 edge[a][b] = 1; 81 out[a]++; 82 in[b]++; 83 DFS_first(a,b+1); 84 } 85 } 86 // 无向图的欧拉回路, cur 点, 从 pos 点开始搜 87 void DFS_two(int cur,int pos) 88 { 89 int i,a,b; 90 stack[top++] = cur; 91 for(i = pos;i<n;i++) 92 { 93 if(edge[cur][i] != 0) 94 { 95 edge[i][cur] = 0; 96 edge[cur][i] = 0; 97 degree[cur]--; 98 degree[i]--; 99 DFS_two(i,0); 100 break; 101 } 102 } 103 if(i==n && top<n) // 走投无路, 而且还有边的时候, 退回一步 104 { 105 b = stack[--top]; 106 a = stack[--top]; 107 edge[a][b] = 1; 108 edge[b][a] = 1; 109 degree[a]++; 110 degree[b]++; 111 DFS_two(a,b+1); 112 } 113 114 } 115 int main() 116 { 117 printf("0, 无向图 1, 有向图 : "); 118 scanf("%d", &type); 119 printf("输入顶点个数: "); 120 scanf("%d",&n); 121 memset(edge,0,sizeof(edge)); 122 memset(degree,0,sizeof(degree)); //无向图的度数 123 memset(in,0,sizeof(in)); //有向图的入度 124 memset(out,0,sizeof(out)); //有向图的出度 125 126 while(true) 127 { 128 int a,b; //边集 129 scanf("%d %d",&a,&b); 130 if(!(a||b)) // 0 0 break 131 { 132 break; 133 } 134 edge[a][b] = 1; 135 in[b]++; 136 out[a]++; 137 if(!type) // 如果是无向图 138 { 139 edge[b][a] = 1; 140 degree[a]++; //无向图的度数 141 degree[b]++; 142 } 143 } 144 if(judge()) 145 { 146 printf("\n一条欧拉回路: "); 147 if(type) 148 DFS_first(0,0); 149 else 150 DFS_two(0,0); 151 for(int i =0; i<top; i++) 152 { 153 printf("%d",stack[i]); 154 if(i+1!=top) 155 printf(" -> "); 156 } 157 putchar(‘\n‘); 158 } 159 else 160 { 161 printf("\n不存在欧拉回路!\n"); 162 } 163 return 0; 164 }
摘自《图论算法理论、实现及应用-王桂平》