在有向图中查找循环，return 语句

Question

我编写了一个工作解决方案来在有向图中找到一个循环，但是我想知道在从递归堆栈中删除一个键后包含 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错误的说法，我想知道为什么要包含它。

谢谢

Answer 1

如果你问原因，显而易见的答案是可读性。

如果没有显式 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 语句

Find cycle in directed graph, return statement

python

graph

cycle

directed-graph