13、弗罗莱(Fleury)算法,求欧拉(Euler)通路/回路

2024-03-06 16:20

本文主要是介绍13、弗罗莱(Fleury)算法,求欧拉(Euler)通路/回路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、基本概念:

1)定义 

欧拉通路 (欧拉迹)—通过图中每条边一次且仅一次,并且过每一顶点的通路。

欧拉回路 (欧拉闭迹)—通过图中每条边一次且仅一次,并且过每一顶点的回路。

欧拉图—存在欧拉回路的图。欧拉图就是从一顶出发每条边恰通过一次又能回到出发顶点的那种图,即不重复的行遍所有的边再回到出发点。

通路和回路-称vie1e2…envj为一条从 vi到 vj且长度为n的通路,其中长度是指通路中边的条数.称起点和终点相同的通路为一条回路

简单图-不含平行边和自回路的图。

混合图-既有有向边,也有无向边的图

平凡图-仅有一个结点的图

完全图-有n个结点的且每对结点都有边相连的无向简单图,称为无向完全图;有n个结点的且每对结点之间都有两条方向相反的边相连的有向简单图为有向完全图。

2)欧拉图的特征:
 无向图

a)G有欧拉通路的充分必要条件为:G 连通,G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。

b)G有欧拉回路(G为欧拉图):G连通,G中均为偶度顶点。 
 有向图

a)D有欧拉通路:D连通,除两个顶点外,其余顶点的入度均等于出度,这两个特殊的顶点中,一个顶点的入度比出度大1,另一个顶点的入度比出度小1。

b)D有欧拉回路(D为欧拉图):D连通,D中所有顶点的入度等于出度。一个有向图是欧拉图,当且仅当该图所有顶点度数都是0。
2、弗罗莱(Fleury)算法思想-解决欧拉回路
    Fleury算法:
   任取v0∈V(G),令P0=v0;

设Pi=v0e1v1e2…ei vi已经行遍,按下面方法从中选取ei+1:

(a)ei+1与vi相关联;

(b)除非无别的边可供行遍,否则ei+1不应该为Gi=G-{e1,e2, …, ei}中的桥(所谓桥是一条删除后使连通图不再连通的边);

(c)当(b)不能再进行时,算法停止。

可以证明,当算法停止时所得的简单回路Wm=v0e1v1e2.emvm(vm=v0)G中的一条欧拉回路,复杂度为O(e*e)

3、欧拉算法C语言描述

void DFS(Graph &G,SqStack &S,int x,int t)

{

       k=0;//一个标志,来标记当前访问的节点是否还有邻接边可供访问

       Push(S,x); //将本次遍历边所经由的点入栈

       for(i=t;i<v;i++) //v是顶点数,e是边数

        if(G[i][x]>0)   

         {

          k=1;

          G[i][x]=0; G[x][i]=0; //此边已访问,删除此边

          DFS(G,S,i,0);//寻找下一条关联的边,本次找到的是与x关联的i,在

                        //下一层中将寻找与i关联的边

          break;

         }//if,for

       if(k==0)       //如果k=0,说明与当前顶点关联的边已穷尽

       {

              Pop(S);

              GetTop(S,m);

              G[x][m]=1;G[m][x]=1;//恢复在上一层中被删除的边

              a=x+1;//如果可能的话,从当前节点的下一条关联边开始搜寻

              if(StackLength(S)!=e)//继续搜寻,边还没有全部遍历完

              {

                     Pop(S); //还原到上一步去

                     DFS(G,S,m,a);//

              }//if

              else   //搜寻完毕,将最后节点也入栈

                     Push(S,x);

       }//if

}//DFS

 

void Euler(Graph &G,int x)

{

//G是存储图的邻接矩阵,都处理成无向图形式,值为1代表有边,0代表无边,不包括自回路,x是出发点

InitStack(S);//用来存放遍历边时依次走过的顶点

DFS(G,S,x,0);//深度优先遍历查找,0是指查询的起点

//输出

 while(!StackEmpty(S))

 {

  GetTop(S,m);

  printf("->v%d",m);

  Pop(S);

 }//while

}//Euler

如下为算法的图示动态过程:

4、欧拉算法的C实现

#include "SqStack.h" //堆栈的常见操作

#include "Queue.h"//队列的常见操作

 

typedef int Graph[200][200];

int v,e;

 

void DFS(Graph &G,SqStack &S,int x,int t)

{

       int k=0,i,m,a;

       Push(S,x);

       for(i=t;i<v;i++)

              if(G[i][x]>0)

              {

                     k=1;

                     G[i][x]=0; //删除此边

                     G[x][i]=0;

                     DFS(G,S,i,0);

                     break;

              }//if,for

       if(k==0)

       {

              Pop(S);

              GetTop(S,m);

              G[x][m]=1;//恢复刚刚删除的边

              G[m][x]=1;

              a=x+1;//从下一条边开始搜寻

              if(StackLength(S)!=e)

              {

                     Pop(S);

                     DFS(G,S,m,a);

              }//if

              else

                     Push(S,x);

       }//if

}//DFS

 

int BFSTest(Graph G)

{

       int a[200],x,i,k=0;

       LinkQueue Q;

       InitQueue(Q);

       EnQueue(Q,0);

       for(i=0;i<v;i++)

              a[i]=0;

       a[0]=1;

       while(!QueueEmpty(Q))

       {

              DeQueue(Q,x);

              for(i=0;i<v;i++)

                     if(G[x][i]>0)

                            if(a[i]!=1)

                            {

                                   a[i]=1;

                                   EnQueue(Q,i);

                            }//if

       }//while

       for(i=0;i<v;i++)

              if(a[i]==0)

              {

                     k=1;

                     break;

              }

       if(k==1) 

              return 0;

       else 

              return 1;

}

 

void Euler(Graph &G,int x) 

{

       int m;

       SqStack S;

       InitStack(S);

       DFS(G,S,x,0);

       printf("该图的一个欧拉回路为:");

       while(!StackEmpty(S))

       {

              GetTop(S,m);

              printf("->v%d",m);

              Pop(S);

       }//while

}

 

void InputM1(Graph &G)

{

 

int h,z;

printf("Please input 顶点数和边数\n");

scanf("%d",&v);

scanf("%d",&e);

for(int i=0;i<v;i++)

       for(int j=0;j<v;j++)

              G[i][j]=0;

 

printf("please int the 邻接矩阵的值(起点(数字终点(数字))\n");

for(int i=0;i<e;i++)

  {

       scanf("%d",&h);

       scanf("%d",&z);

       G[h-1][z-1]=1;

          G[z-1][h-1]=1;

  }//for

}//InputM1

 

int main()

{

       int i,j,sum,k=0;

       Graph G;

       InputM1(G);

       if(BFSTest(G)==0) 

       {

              printf("该图不是连通图!\n");

              exit(0);

       }//if

       for(i=0;i<v;i++)

       {

              sum=0;

              for(j=0;j<v;j++)

                     sum+=G[i][j];

              if(sum%2==1)

              {     k=1;

                     break;

              }//if

       }//for

       if(k==1) printf("该图不存在欧拉回路!\n");

       else

              Euler(G,0); //从那个点出发

return 1;

}

顶点数5,边数为6

相关联的点1 2

                             1 3

                             2 5

                             4 2

                             3 2

                             4 5

运行结果(略)

5、小常识:欧拉算法的起由及一笔画问题

七桥问题:18世纪著名古典数学问题之一。在哥尼斯堡的一个公园里,有七座桥将普雷格尔河中两个岛及岛与河岸连接起来(如图)。问是否可能从这四块陆地中任一块出发,恰好通过每座桥一次,再回到起点?欧拉于1736年研究并解决了此问题,他把问题归结为如下右图的“一笔画”问题,证明上述走法是不可能的。

一笔划

⒈凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。

⒉凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。

⒊其他情况的图都不能一笔画出。(奇点数除以二便可算出此图需几笔画成。)

6、欧拉回路和Hamilton(汉密尔顿)回路

汉密尔顿图与欧拉图的区别只在于,边与顶点的区别,欧拉图是每边经过一次,汉密尔顿图是每顶经过一次。

这篇关于13、弗罗莱(Fleury)算法,求欧拉(Euler)通路/回路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/780621

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc