我在Python中有这段代码。用户编写图的附加列表，并获取图是否具有欧拉电路、欧拉路径或不是欧拉路径的信息。一切都很好，直到我最后写了这篇文章： ln1 = [1， 2， 1， 6， 2， 3， 3， 4， 4， 5， 5， 6] 输出应为：图有一个欧拉电路。 你能纠正这个代码吗？我不知道问题是什么
# Python program to check if a given graph is Eulerian or not
# Complexity : O(V+E)
from collections import defaultdict
# This class represents a undirected graph using adjacency list
representation
class Graph:
def __init__(self, vertices):
self.V = vertices # No. of vertices
self.graph = defaultdict(list) # default dictionary to store graph
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
# A function used by isConnected
def DFSUtil(self, v, visited):
# Mark the current node as visited
visited[v] = True
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
'''Method to check if all non-zero degree vertices are
connected. It mainly does DFS traversal starting from
node with non-zero degree'''
def isConnected(self):
# Mark all the vertices as not visited
visited = [False] * (self.V)
# Find a vertex with non-zero degree
for i in range(self.V):
if len(self.graph[i]) > 1:
break
# If there are no edges in the graph, return true
if i == self.V - 1:
return True
# Start DFS traversal from a vertex with non-zero degree
self.DFSUtil(i, visited)
# Check if all non-zero degree vertices are visited
for i in range(self.V):
if visited[i] == False and len(self.graph[i]) > 0:
return False
return True
'''The function returns one of the following values
0 --> If grpah is not Eulerian
1 --> If graph has an Euler path (Semi-Eulerian)
2 --> If graph has an Euler Circuit (Eulerian) '''
def isEulerian(self):
# Check if all non-zero degree vertices are connected
if self.isConnected() == False:
return 0
else:
# Count vertices with odd degree
odd = 0
for i in range(self.V):
if len(self.graph[i]) % 2 != 0:
odd += 1
'''If odd count is 2, then semi-eulerian.
If odd count is 0, then eulerian
If count is more than 2, then graph is not Eulerian
Note that odd count can never be 1 for undirected graph'''
if odd == 0:
return 2
elif odd == 2:
return 1
elif odd > 2:
return 0
# Function to run test cases
def test(self):
res = self.isEulerian()
if res == 0:
print "graph is not Eulerian"
elif res == 1:
print "graph has a Euler path"
else:
print "graph has a Euler cycle"
ln1 = [1, 2, 1, 6, 2, 3, 3, 4, 4, 5, 5, 6]
#ln1 = [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 1, 2, 1, 4, 1, 5, 2, 3, 2, 4, 3, 5, 4, 5] #euler path
#ln1 = [1, 2, 1, 3, 1, 4, 1, 5, 1, 6, 2, 3, 2, 5, 2, 6, 3, 4, 3, 5, 4, 6, 5, 6] #euler path
g1 = Graph(len(ln1)/2)
i = 0
j = 1
while i + 2 <= len(ln1) and j + 1 <= len(ln1):
g1.addEdge(ln1[i], ln1[j])
i += 2
j += 2
g1.test()
您是否尝试过用visited = [False] * int(self.V)替换visited = [False] * (self.V)？
由于此问题不仅发生在这一行，因此您可能应该使用以下方法初始化您的类：
self.V = int(vertices) # No. of vertices
恕我直言，顶点的数量无论如何都应该是一个整数。
但似乎还有更多的问题。例如，您在if子句之后有一个isConnectedreturn语句，该语句取决于i。但是i之前在循环中使用过。所以这应该只有效，如果它真的只取决于最后一个索引(在这种情况下似乎没问题(。
此外，您不会将更改保存到visited因为它是方法变量而不是实例变量。因此，visited将保持设置为False.
下一个问题：在DFSUtil
# Recur for all the vertices adjacent to this vertex
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
例如，从self.graph[v]返回一个包含[0, 6]的列表 forv=5。但索引6超出了长度为 6 的visited的范围。
我已经修改了DFSUtil循环并将v更改为v+1：
for i in self.graph[v+1]:
if visited[i] == False:
self.DFSUtil(i, visited)
现在程序启动，但在输出中它说："图形不是欧拉"。它当然应该说"图有一个欧拉电路"。