《欧拉路径和欧拉回路.pptx》由会员分享，可在线阅读，更多相关《欧拉路径和欧拉回路.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1欧拉路径和欧拉回路欧拉路径和欧拉回路欧拉路径和欧拉回路的定义：欧拉路径和欧拉回路的定义：n n一副图，寻找一条只通过每条边一次的路径叫做欧拉路径如果这条路径的起点和终点是同一点，那么这条路径叫做欧拉回路第1页/共40页怎么样判断是否存在欧拉回路怎么样判断是否存在欧拉回路n n在以下三种情况中有三种不同的算法：无向图有向图混合图注：前两种的判定很简单，第三种稍复杂一些，但是可转化为前两种的情况(第三种只是简要说明)第2页/共40页无向图无向图n n每个顶点的入度是偶数，则存在欧拉回路n n证明很简单：其原理就是每个顶点要进去多少次，就必须出来多少次如果存在度为奇数的顶点，那么必有通过某一
2、边进入这一点后，没有边可以出去，这样就不会有回路第3页/共40页有向图有向图n n每个顶点的入度和出度相等n n原理同无向图也是有多少边进入，就要有多少边出去n n对于混合图这里就不祥细说明了第4页/共40页混合图混合图n n混合图的定义：n n有的边是有向的，有的边是无向的。例如城市里的交通网络，有的路是单行道，有的路是双行道。n n找到一个给每条无向的边定向的策略，使得每个顶点的入度等于出度，这样就能转换成上面第二种情况。第5页/共40页关于欧拉路径关于欧拉路径n n源点与汇点不为同一点n n判定一个图是否有欧拉路径n n一个无向图中除源点与汇点的度数为奇数外，其于点的度数都为偶数，那么则
3、存在欧拉路径第6页/共40页怎么样求欧拉回路怎么样求欧拉回路n n就是循环地找到出发点n n一个解决此类问题基本的想法是从某个节点开始,然后查出一个从这个点出发回到这个点的环路径。这种方法保证每个边都被遍历.如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。第7页/共40页具体步骤具体步骤n n如果此时与该点无相连的点，那么就加入路径中n n如果该点有相连的点，那么就列一张表，遍历这些点，直到没有相连的点n n处理当前的点，删出走过的这条边，并在其相临的点上进行同样的操作并把删除的点加入到路径中去n n其实
4、这就是一个递归过程第8页/共40页n n但选择起点时要注意如果所有点的度数为偶数，那么可以依题意随意选择，都可得到一条欧拉回路n n如果有的点度数为奇数，那么先判定是否存在欧拉路径，如果存在，那么起点必须从度数为奇数的点开始第9页/共40页来自上的例子来自上的例子n n考虑左边的图，每个点的度都为考虑左边的图，每个点的度都为偶数则存在欧拉路径偶数则存在欧拉路径第10页/共40页来自上的例子来自上的例子n nStack:Stack:Location:1 Location:1 Circuit:Circuit:第11页/共40页来自上的例子来自上的例子n nStack:1 Stack:1 Locat
5、ion:4 Location:4 Circuit:Circuit:第12页/共40页来自上的例子来自上的例子n nStack:1 4 Stack:1 4 Location:2 Location:2 Circuit:Circuit:第13页/共40页来自上的例子来自上的例子n nStack:1 4 2 Stack:1 4 2 Location:5 Location:5 Circuit:Circuit:第14页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 Stack:1 4 2 5 Location:1 Location:1 Circuit:Circuit:第15页/共40页
6、来自上的例子来自上的例子n nStack:1 4 2 Stack:1 4 2 Location:5 Location:5 Circuit:1 Circuit:1 第16页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 Stack:1 4 2 5 Location:6 Location:6 Circuit:1 Circuit:1 第17页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 Stack:1 4 2 5 6 Location:2 Location:2 Circuit:1 Circuit:1 第18页/共40页来自上的例子来自上的例子n nSta
7、ck:1 4 2 5 6 2 Stack:1 4 2 5 6 2 Location:7 Location:7 Circuit:1 Circuit:1 第19页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 Stack:1 4 2 5 6 2 7 Location:3 Location:3 Circuit:1 Circuit:1 第20页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 Stack:1 4 2 5 6 2 7 3 Location:4 Location:4 Circuit:1 Circuit:1 第21页/共40页
8、来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 4 Stack:1 4 2 5 6 2 7 3 4 Location:6 Location:6 Circuit:1 Circuit:1 第22页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 4 6 Stack:1 4 2 5 6 2 7 3 4 6 Location:7 Location:7 Circuit:1 Circuit:1 第23页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 4 Stack:1 4 2 5 6 2 7 3 4 6 6 7
9、 7 Location:5 Location:5 Circuit:1 Circuit:1 第24页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 4 6 Stack:1 4 2 5 6 2 7 3 4 6 Location:7 Location:7 Circuit:1 5 Circuit:1 5 第25页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 3 4 Stack:1 4 2 5 6 2 7 3 4 Location:6 Location:6 Circuit:1 5 7Circuit:1 5 7第26页/共40页来自上的
10、例子来自上的例子n nStack:1 4 2 5 6 2 7 3 Stack:1 4 2 5 6 2 7 3 Location:4 Location:4 Circuit:1 5 7 6 Circuit:1 5 7 6 第27页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 7 Stack:1 4 2 5 6 2 7 Location:3 Location:3 Circuit:1 5 7 6 4 Circuit:1 5 7 6 4 第28页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 2 Stack:1 4 2 5 6 2 Location:
11、7 Location:7 Circuit:1 5 7 6 4 3 Circuit:1 5 7 6 4 3 第29页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 6 Stack:1 4 2 5 6 Location:2 Location:2 Circuit:1 5 7 6 4 3 7 Circuit:1 5 7 6 4 3 7 第30页/共40页来自上的例子来自上的例子n nStack:1 4 2 5 Stack:1 4 2 5 Location:6 Location:6 Circuit:1 5 7 6 4 3 7 2 Circuit:1 5 7 6 4 3 7 2 第31
12、页/共40页来自上的例子来自上的例子n nStack:1 4 2 Stack:1 4 2 Location:5 Location:5 Circuit:1 5 7 6 4 3 7 2 6 Circuit:1 5 7 6 4 3 7 2 6 第32页/共40页来自上的例子来自上的例子n nStack:1 4 Stack:1 4 Location:2 Location:2 Circuit:1 5 7 6 4 3 7 2 6 5 Circuit:1 5 7 6 4 3 7 2 6 5 第33页/共40页来自上的例子来自上的例子n nStack:1 Stack:1 Location:4 Location
13、:4 Circuit:1 5 7 6 4 3 7 2 6 5 2 Circuit:1 5 7 6 4 3 7 2 6 5 2 第34页/共40页来自上的例子来自上的例子n nStack:Stack:Location:1 Location:1 Circuit:1 5 7 6 4 3 7 2 6 5 2 4 Circuit:1 5 7 6 4 3 7 2 6 5 2 4 第35页/共40页来自上的例子来自上的例子n nStack:Stack:Location:Location:Circuit:1 5 7 6 4 3 7 2 6 5 2 4 1 Circuit:1 5 7 6 4 3 7 2 6 5
14、 2 4 1 第36页/共40页伪代码伪代码n nfind_circuit(node i)find_circuit(node i)如果当前结点没有边如果当前结点没有边将其加入到路径中将其加入到路径中否则：否则：while(node i while(node i 没有相连的边没有相连的边)j j是与是与i i相临的顶点（即相临的顶点（即i,j i,j之间有一条边）之间有一条边）find_circuit(j);find_circuit(j);删除删除i i和和j j之间的边之间的边 将将i i加入路径中去加入路径中去 第37页/共40页n nvoid solve(int x)void solve(
15、int x)n n n n if(matchx=0)if(matchx=0)n n n n RecordRecordPos=x;RecordRecordPos=x;n n RecordPos+;RecordPos+;n n n n n n else elsen n n n for(int k=0;k=500;k+)for(int k=0;k=500;k+)n n n n if(Arrayxk!=0)if(Arrayxk!=0)n n n n Arrayxk-;Arrayxk-;n n Arraykx-;Arraykx-;n n matchx-;matchx-;n n matchk-;matchk-;n n solve(k);solve(k);n n n n n n n n RecordRecordPos=x;RecordRecordPos=x;n n RecordPos+;RecordPos+;n n n n 第38页/共40页n n Q&A第39页/共40页