在有向图中查找循环,return 语句
Find cycle in directed graph, return statement
我编写了一个工作解决方案来在有向图中找到一个循环,但是我想知道在从递归堆栈中删除一个键后包含 return 错误语句的原因。
class vertex:
def __init__(self, key):
self.neighbours = {}
self.key = key
def add(self, key, edge):
self.neighbours[key] = edge
class graph:
def __init__(self):
self.root = {}
self.nbnodes = 0
def addnode(self, key1, key2, edge=0):
if key1 not in self.root:
self.root[key1] = vertex(key1)
self.nbnodes += 1
if key2 not in self.root:
self.root[key2] = vertex(key2)
self.nbnodes += 1
self.root[key1].add(key2, edge)
def dfs(self):
visited = set()
recstack = []
for key in self.root:
if key not in visited:
if self._dfs(key, visited, recstack):
print('cycle')
else:
print('No cycle')
def _dfs(self, key, visited, recstack):
visited.add(key)
recstack.append(key)
for neighbour in self.root[key].neighbours:
if neighbour not in visited:
if self._dfs(neighbour, visited, recstack):
return True
elif neighbour in recstack:
return True
recstack.remove(key)
#return False
if __name__ == '__main__':
a = graph()
a.addnode(0,1)
a.addnode(0,2)
a.addnode(1,3)
a.addnode(1,4)
a.addnode(2,4)
a.addnode(4,5)
a.dfs()
以上是我最终的解决代码,我注释掉了return错误的说法,我想知道为什么要包含它。
谢谢
如果你问原因,显而易见的答案是可读性。
如果没有显式 return False
,您将隐式 returning None
,因此片段 if self._dfs(neighbour, visited, recstack):
的工作方式与评论的 return False
相同.我仍然不清楚其意图,并假设您忘记了 return 它(或者想指出 reader 在这种情况下没有功能状态)。
引用 documentation:
None is frequently used to
represent the absence of a value, as when default arguments are not
passed to a function. Assignments to None are illegal and raise a
SyntaxError.
你的价值没有缺席,它完美的定义了你的功能。除了遵循良好做法外,它不会更改您的代码中的任何内容。
顺便说一句。 类 的名称通常是大写和 CamelCase,而函数使用 snake_case.
我编写了一个工作解决方案来在有向图中找到一个循环,但是我想知道在从递归堆栈中删除一个键后包含 return 错误语句的原因。
class vertex:
def __init__(self, key):
self.neighbours = {}
self.key = key
def add(self, key, edge):
self.neighbours[key] = edge
class graph:
def __init__(self):
self.root = {}
self.nbnodes = 0
def addnode(self, key1, key2, edge=0):
if key1 not in self.root:
self.root[key1] = vertex(key1)
self.nbnodes += 1
if key2 not in self.root:
self.root[key2] = vertex(key2)
self.nbnodes += 1
self.root[key1].add(key2, edge)
def dfs(self):
visited = set()
recstack = []
for key in self.root:
if key not in visited:
if self._dfs(key, visited, recstack):
print('cycle')
else:
print('No cycle')
def _dfs(self, key, visited, recstack):
visited.add(key)
recstack.append(key)
for neighbour in self.root[key].neighbours:
if neighbour not in visited:
if self._dfs(neighbour, visited, recstack):
return True
elif neighbour in recstack:
return True
recstack.remove(key)
#return False
if __name__ == '__main__':
a = graph()
a.addnode(0,1)
a.addnode(0,2)
a.addnode(1,3)
a.addnode(1,4)
a.addnode(2,4)
a.addnode(4,5)
a.dfs()
以上是我最终的解决代码,我注释掉了return错误的说法,我想知道为什么要包含它。
谢谢
如果你问原因,显而易见的答案是可读性。
如果没有显式 return False
,您将隐式 returning None
,因此片段 if self._dfs(neighbour, visited, recstack):
的工作方式与评论的 return False
相同.我仍然不清楚其意图,并假设您忘记了 return 它(或者想指出 reader 在这种情况下没有功能状态)。
引用 documentation:
None is frequently used to represent the absence of a value, as when default arguments are not passed to a function. Assignments to None are illegal and raise a SyntaxError.
你的价值没有缺席,它完美的定义了你的功能。除了遵循良好做法外,它不会更改您的代码中的任何内容。
顺便说一句。 类 的名称通常是大写和 CamelCase,而函数使用 snake_case.