欧拉环游:在图中找到一条路径,从起点开始,依此经过图中的所有边,一个边只能走一次,到达终点,终点和起点可以不同
欧拉回路:在图中找到一条路径,从起点开始,依此经过图中的所有边,最后回到起点,一个边只能走一次。
欧拉环游存在的条件:当前图是连通的,图中的恰有零个或两个顶点的度是奇数,其余顶点的度数为偶数,才会存在
欧拉回路存在的条件:当前图是连通的,图中所有的顶点的度是偶数时,欧拉回路必存在。
寻找欧拉回路的算法:如果从起点出发的所有边均已用完,那么图中就会有的部分遍历不到。最容易补救的方法就是找出有尚未访问的边的路径上的第一个顶点,并执行另外一次深度优先搜索。这将给出另外一个回路,把它拼接到原来的回路上。
继续该过程直到所有的边都被遍历到为止。
用到的数据结构
typedef struct Node* ptrNode;
struct Node {
int v; //记录顶点
ptrNode next;
};
//用链表来存储欧拉回路走过的路径,head为链表的头节点
ptrNode head = (ptrNode)malloc(sizeof(struct Node));
ptrNode H = head;
//首先判断图是否为连通的,然后判断图中顶点的度是否都为偶数
int Viseted[MAXVERTEX]; //用一次dfs,记录图是否连通
int degree[MAXVERTEX]; //记录每个顶点的度
int ne; //ne记录走过的边
Graph P; //邻接矩阵存储图
主函数步骤
int main() {
P = BuildGraph(); //初始化图
if (IsConnect()) { //IsConnect 函数判断图是否连通
if (Isdegree()) { //Isdegree 函数判断每个顶点的度是否为偶数
printf("存在欧拉回路\n");
isDfs(0); //如果存在欧拉回路,从顶点0开始寻找欧拉回路
}
else {
printf("图中节点的度数不为偶数,欧拉回路不存在\n");
}
}
else {
printf("该图不连通,无欧拉回路\n");
}
return 0;
}
判断图是否连通函数
void dfs(int vertex) { //对图进行一次dfs,判断图是否连通
Viseted[vertex] = 1;
for (int i = 0; i < P->Nv; i++) {
if (P->Graph[vertex][i] != 0 && Viseted[i] == 0) {
dfs(i);
}
}
}
bool IsConnect() {
dfs(0); //进行一次dfs,然后判断,每个顶点是否都已访问到
for (int i = 0; i < P->Nv; i++) {
if (Viseted[i] == 0)
return false;
}
return true;
}
判断图中顶点度的个数是否为偶数
bool Isdegree() {
//判断图中各个顶点的度是否为偶数
for (int i = 0; i < P->Nv; i++) {
for (int j = 0; j < P->Nv; j++) {
if (P->Graph[i][j] != 0) {
//i到j有一条边。
degree[j]++;
}
}
}
for (int i = 0; i < P->Nv;i++) {
if (degree[i] % 2 != 0) {
return false;
}
}
return true;
}
求欧拉回路函数
void Dfs(int vertex) {
//将走过的顶点,加入链表
ptrNode p = (ptrNode)malloc(sizeof(struct Node));
p->v = vertex;
p->next = NULL;
H->next = p;
H = p;
for (int i = 0; i < P->Nv; i++) {
if (P->Graph[vertex][i] != 0) {
P->Graph[vertex][i] = 0; //将边删除
P->Graph[i][vertex] = 0; //将边删除
ne += 2; //统计当前走过的边数
Dfs(i);
break; //每个顶点不能往后再走
}
}
}
void euler(int vertex) {
//求欧拉回路路径
Dfs(vertex);
int flag;
ptrNode p,tmp,f=NULL;
while (ne < P->Ne * 2) {
for (p = head->next; p; p = p->next) {
//找出从路径开始的第一个尚未走过边的顶点
flag = 0;
for (int i = 0; i < P->Nv; i++) {
if (P->Graph[p->v][i] != 0) {
//顶点p->v有边尚未走过
f = H; //记录当前链表尾的位置
flag = 1; //找到尚未走过的边的顶点
Dfs(p->v); //p->v进行一次dfs
break;
}
}
if (flag == 1)
break;
}
//此时f->next为从p->v顶点开始走过的路径
//p为链表中要拼接的位置
tmp = f;
f = f->next->next;
//将f拼接到p后面
tmp->next = NULL; //将链表尾置位空
H = tmp; //H为新拼接后的链表尾
tmp = p->next; //保存p->next
p->next = f;
while (p->next)
p = p->next;
p->next = tmp; //将tmp接回p->next
}
//输出欧拉回路
for (p = head->next; p;p = p->next) {
printf("%d ", p->v);
}
}