没有合适的资源?快使用搜索试试~ 我知道了~
2. 求解算法思想 1.对于无向图,判断度数为奇数的点的个数,若为0,则设任意一点为起点,若为2,则从这2个点中 2.从起点开始进行递归:对于当前节点x,扫描与
资源详情
资源评论
资源推荐
图的遍历调研
第十四周讨论课个人资料
一 一笔画问题
1. 概述:
• 图论起源于18世纪,1736年瑞士数学家欧拉(Euler)发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯
堡城有一条横贯全市的普雷格尔河,河中的两个岛与两岸用七座桥连结起来。当时那里的居民热衷于一个难题:有游人怎
样不重复地走遍七桥,最后回到出发点。
[1]
• 为了解决这个问题,欧拉用 A,B,C,D 4个字母代替陆地,作为 4 个顶点,将联结两块陆地的桥用相应的线段表示,于
是哥尼斯堡七桥问题就变成了图中,是否存在经过每条边一次且仅一次,经过所有的顶点的回路问题了。欧拉在论文中指
出,这样的回路是不存在的。
• 什么是欧拉路径?欧拉路径就是一条能够不重不漏地经过图上的每一条边的路径,即小学奥数中的一笔画问题。而若
这条路径的起点和终点相同,则将这条路径称为欧拉回路。
• 数学家欧拉找到一笔画的规律是:
⚫ 凡是由偶点组成的连通图,一定可以一笔画成。画时可以把任一偶点为起点,最后一定能以这个点为终点画完此图。
⚫ 凡是只有两个奇点的连通图(其余都为偶点),一定可以一笔画成。画时必须把一个奇点为起点,另一个奇点终点。
⚫ 其他情况的图都不能一笔画出。(有偶数个奇点除以二可以算出此图至少需几笔画成。)
2. 求解算法思想
查找欧拉路径的算法有Fluery算法和Hierholzer算法。
[2]
Hierholzer算法流程:
1.对于无向图,判断度数为奇数的点的个数,若为0,则设任意一点为起点,若为2,则从这2个点中
任取一个作为起点;对于有向图,判断入度和出度不同的点的个数,若为0,则设任意一点为起点,
若为2,则设入度比出度小1的点为起点,另一点为终点。具体起点的选择要视题目要求而定。
2.从起点开始进行递归:对于当前节点x,扫描与x相连的所有边,当扫描到一条(x,y)时,删除该边,
并递归y。扫描完所有边后,将x加入答案队列。
3.倒序输出答案队列。(因为这里是倒序输出,我们可以用栈来存储答案,当然用双端队列也可以)
解析:
从起点开始,每一次执行递归函数,相当于模拟一笔画的过程。递归的边界显然就是路径的终点,
对于一个有欧拉路径的图,此时图上的所有边都已被删除,自然就不能继续递归。由于存储答案是
在遍历以后进行的,答案存储也就是倒序的,因此要倒序输出答案。
Fleury算法流程:
1. 任取G中一个点x
2. 选择一条从点x出发的边i(若i可以不为桥则不应将i选为桥),设i连向点y,删除i,
然后:
1)i不为桥,走到点y;
2)i迫不得已必须为桥,走到点y并删去点x(因为删去i后,点x将成为孤立点)。
3. 步骤2无法执行时停止算法
当算法停止时,依次经过的点所得到的简单回路为图G的一条欧拉回路。
剩余53页未读,继续阅读
艾法
- 粉丝: 20
- 资源: 319
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0