《欧拉路径和欧拉回路课件》由会员分享，可在线阅读，更多相关《欧拉路径和欧拉回路课件（40页珍藏版）》请在金锄头文库上搜索。
1、浅谈欧拉路径浅谈欧拉路径5050309760 李冰欧拉路径和欧拉回路的定义：欧拉路径和欧拉回路的定义：l一副图，寻找一条只通过每条边一次的路径叫做欧拉路径如果这条路径的起点和终点是同一点，那么这条路径叫做欧拉回路怎么样判断是否存在欧拉回路怎么样判断是否存在欧拉回路l在以下三种情况中有三种不同的算法：无向图有向图混合图注：前两种的判定很简单，第三种稍复杂一些，但是可转化为前两种的情况(第三种只是简要说明)无向图无向图l每个顶点的入度是偶数，则存在欧拉回路l证明很简单：其原理就是每个顶点要进去多少次，就必须出来多少次如果存在度为奇数的顶点，那么必有通过某一边进入这一点后，没有边可以出去，这样就不会
2、有回路有向图有向图l每个顶点的入度和出度相等l原理同无向图也是有多少边进入，就要有多少边出去l对于混合图这里就不祥细说明了混合图混合图l混合图的定义：l有的边是有向的，有的边是无向的。例如城市里的交通网络，有的路是单行道，有的路是双行道。l找到一个给每条无向的边定向的策略，使得每个顶点的入度等于出度，这样就能转换成上面第二种情况。关于欧拉路径关于欧拉路径l源点与汇点不为同一点l判定一个图是否有欧拉路径l一个无向图中除源点与汇点的度数为奇数外，其于点的度数都为偶数，那么则存在欧拉路径怎么样求欧拉回路怎么样求欧拉回路l就是循环地找到出发点l一个解决此类问题基本的想法是从某个节点开始,然后查出一个从
3、这个点出发回到这个点的环路径。这种方法保证每个边都被遍历.如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤具体步骤l如果此时与该点无相连的点，那么就加入路径中l如果该点有相连的点，那么就列一张表，遍历这些点，直到没有相连的点l处理当前的点，删出走过的这条边，并在其相临的点上进行同样的操作并把删除的点加入到路径中去l其实这就是一个递归过程l但选择起点时要注意如果所有点的度数为偶数，那么可以依题意随意选择，都可得到一条欧拉回路l如果有的点度数为奇数，那么先判定是否存在欧拉路径，如果存在，那么起点必须
4、从度数为奇数的点开始来自上的例子来自上的例子l考虑左边的图，每个点的度都为偶数则存在欧拉路径来自上的例子来自上的例子lStack: Location: 1 Circuit: 来自上的例子来自上的例子lStack: 1 Location: 4 Circuit: 来自上的例子来自上的例子lStack: 1 4 Location: 2 Circuit: 来自上的例子来自上的例子lStack: 1 4 2 Location: 5 Circuit: 来自上的例子来自上的例子lStack: 1 4 2 5 Location: 1 Circuit: 来自上的例子来自上的例子lStack: 1 4 2 Loc
5、ation: 5 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 Location: 6 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 Location: 2 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 Location: 7 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 Location: 3 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 Location: 4 Circuit: 1 来自上的例
6、子来自上的例子lStack: 1 4 2 5 6 2 7 3 4 Location: 6 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 4 6 Location: 7 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 4 6 7 Location: 5 Circuit: 1 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 4 6 Location: 7 Circuit: 1 5 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 4 Location: 6 C
7、ircuit: 1 5 7来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 3 Location: 4 Circuit: 1 5 7 6 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 7 Location: 3 Circuit: 1 5 7 6 4 来自上的例子来自上的例子lStack: 1 4 2 5 6 2 Location: 7 Circuit: 1 5 7 6 4 3 来自上的例子来自上的例子lStack: 1 4 2 5 6 Location: 2 Circuit: 1 5 7 6 4 3 7 来自上的例子来自上的例子lStack: 1 4 2 5
8、 Location: 6 Circuit: 1 5 7 6 4 3 7 2 来自上的例子来自上的例子lStack: 1 4 2 Location: 5 Circuit: 1 5 7 6 4 3 7 2 6 来自上的例子来自上的例子lStack: 1 4 Location: 2 Circuit: 1 5 7 6 4 3 7 2 6 5 来自上的例子来自上的例子lStack: 1 Location: 4 Circuit: 1 5 7 6 4 3 7 2 6 5 2 来自上的例子来自上的例子lStack: Location: 1 Circuit: 1 5 7 6 4 3 7 2 6 5 2 4 来自
9、上的例子来自上的例子lStack: Location: Circuit: 1 5 7 6 4 3 7 2 6 5 2 4 1 伪代码伪代码lfind_circuit(node i) 如果当前结点没有边将其加入到路径中否则：while(node i 没有相连的边) j是与i相临的顶点（即i,j之间有一条边） find_circuit(j); 删除i和j之间的边 将i加入路径中去lvoid solve(int x)ll if(matchx = 0)l l RecordRecordPos = x;l RecordPos+;l l l elsel l for(int k =0;k=500;k+)l l if(Arrayxk !=0 )l l Arrayxk-;l Arraykx-;l matchx-;l matchk-;l solve(k); l l l l RecordRecordPos = x;l RecordPos+; l l l Q & A
