《欧拉路径(欧拉回路)算法.doc》由会员分享，可在线阅读，更多相关《欧拉路径(欧拉回路)算法.doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流欧拉路径(欧拉回路)算法.精品文档.欧拉路径（欧拉回路）相关定义： 若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉回路。具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。判断图是否为欧拉图：无向图为欧拉图，当且仅当为连通图且所有顶点的度为偶数。无向图为半欧拉图，当且仅当为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。有向图为欧拉图，当且仅当其基图（忽略有向图所有边的方向，得到的无向图称为该有向图的基图）连通，且所有顶点的入度等于出度。有
2、向图为半欧拉图，当且仅当其基图连通，且有且仅有一个顶点的入度比出度大1、有且仅有一个顶点的入度比出度小1，其它所有顶点的入度等于出度。欧拉回路（路径）的算法：有向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。第二步，如果存在欧拉路径，从入度比出度小1的点开始BFS；如果存在欧拉回路，从任意一点开始。第三步，设DFS到点u，遍历u的出边e(u,v)。第四步，如果e未被标记，转到第五步，否则转到第三步。第五步，标记e(u,v)，DFS点v。第六步，边e(u,v)入栈。第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。无向图：第一步，判断是否存在欧拉路径（欧拉回路），如果不存在，算法结束。第二步，如果存在欧拉路径，从度为奇数的点开始BFS；如果存在欧拉回路，从任意一点开始。第三步，设DFS到点u，遍历u的出边e(u,v)。第四步，如果e未被标记，转到第五步，否则转到第三步。第五步，标记e(u,v)及它的反向边，DFS点v。第六步，边e(u,v)入栈。第七步，完成DFS后，从栈顶顺序输出边构成一个欧拉路径（欧拉回路）。