admin 管理员组

文章数量: 1184232

欧拉回路python

  • 定义

    • 如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
    • 如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。 [1]
    • 具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。

  • 判断

    A.判断欧拉通路是否存在的方法

    有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。

    无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。

    B.判断欧拉回路是否存在的方法

    有向图：图连通，所有的顶点出度=入度。

    无向图：图连通，所有顶点都是偶数度。

python代码参考：欧拉回路，欧拉道路，七桥问题，Python代码实现_曹向前的博客-CSDN博客

以七桥问题为例，选择一个奇数点开始，使用dfs思想，对每个可能的路深度遍历

def isEuler():allVisited = Truefor e in visited:if e == 0:allVisited = Falseif allVisited:if queue[0] == queue[len(queue) - 1]:return 1else:return 2return 0def printPath(flag):if flag == 1:print("是欧拉回路:", end="")else:print("是欧拉道路:", end="")for i in range(len(queue)):if i < len(queue) - 1:print(queue[i], "-> ", end="")else:print(queue[i])def dfs(x):queue.append(x)flag = isEuler()if flag > 0:eulerFlag = TrueprintPath(flag)for i in range(len(eulerEdges)):if visited[i]:continuevisited[i] = 1if eulerEdges[i][0] == x:dfs(eulerEdges[i][1])queue.pop()visited[i] = 0elif eulerEdges[i][1] == x:dfs(eulerEdges[i][0])queue.pop()visited[i] = 0eulerEdges = [(1, 2),(1, 2),(1, 0),(2, 0),(2, 3),(2, 3),(3, 0)
]      
queue = []
visited = [0 for _ in range(len(eulerEdges))]
eulerFlag = False
start = 1dfs(start)
if not eulerFlag:print("不是欧拉回路或欧拉道路")

本文标签： 欧拉回路python

版权声明：本文标题：欧拉回路python 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.roclinux.cn/b/1686635400a20007.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。