首页 > 代码库 > 欧拉回路
欧拉回路
定义
欧拉回路:图G,若存在一条路,经过G中每条边有且仅有一次,称这条路为欧拉路,如果存在一条回路经过G每条边有且仅有一次,称这条回路为欧拉回路。具有欧拉回路的图成为欧拉图。
判断原理
有向图:图连通,有一个顶点出度大入度1,有一个顶点入度大出度1,其余都是出度=入度。 无向图:图连通,只有两个顶点是奇数度,其余都是偶数度的。
常用处理流程
1.使用DFS或并查集判断连通性 2.判定度数是否满足条件 3.获取回路 void euler(int u){ for(int v = 0;v < n; v++) if(G[u][v] && !vis[u][v]){ vis[u][v] = vis[v][u] = 1 /* vis[u][v] = 1 for 有向图*/ euler(v); cout << u << "->" "v" << endl; } }
欧拉回路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。