首页 > 代码库 > 欧拉回路（Euler Circuit）
欧拉回路（Euler Circuit）
定义：若一副图中从某个顶点A走出，经过图中的所有的边，且每条边只经过一次，则称这个环为欧拉回路，如果某幅图含有这样的环，则这幅图叫做欧拉图。
如何判断一幅图是不是欧拉图，也即一幅图中是否含有欧拉回路。
- 如果一幅图中所有顶点的出度等于入度，且此图为强连通图，则此图含有欧拉回路，这幅图为欧拉图。
判断是否为存在欧拉回路可以直接利用上面的判断定理，但是打印出相应的路径就相对困难一些。
假设图G为一副含有欧拉回路的图，也即欧拉图。
- 随机选取G中的一个顶点A，如果A不存在没有访问过的边，则将A加入路径
- 如果A存在没有访问过的边，则随机取出A的一条未访问过的边进行访问，此时访问的顶点为B。
- 重复上述两步，直到所有的边都被访问过为止。
- 此时就得到了相应的欧拉回路。
- 首先随机选择一个顶点A，进行路径寻找，最终会找到一个以A为起点和终点的环。
- 此时如果不存在没有访问过的边，则这个环就为欧拉环。
- 如果存在没有访问过的边，则我们可以知道，要想得到完整的欧拉环，必须先访问未访问过的边，为此说明此时的环A中含有某个顶点C，其存在没有访问过的边
- 从C开始访问C未访问过的边，必得到一个以C为起点和终点的环，此时将这个环加入到A中，这就得到了我们想要的欧拉环。
如上图所示，先访问顶点A，之后得到红色的环，此时C,D,E三个顶点组成的环没有被访问，且C存在未被访问的边，因此在欧拉回路中，C,D,E组成的环应该先被访问，为此将A,B加入路径，然后C开始访问D,E,C，分别将之后分别将其压入路径，从而得到想要的路径为A,C,D,E,C,B,A。
欧拉回路（Euler Circuit）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。