如何使用Python检测有向图中的循环? [英] How to detect a cycle in a directed graph with Python?

问题描述

我有一些输入，例如:[('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')].我要查找的是此edgeList表示的有向图中是否存在循环.

I have some input like: [('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]. I want to look for if the existence of a cycle in a directed graph represented by this edgeList.

我阅读了一个讨论: https://www.geeksforgeeks.org /detect-cycle-in-a-graph/，但是在以下情况下会出现一些错误:

I read a discussion: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/, however it has some errors when the case is:

g = Graph(3)
g.addEdge('A', 'B')
g.addEdge('B', 'C')
g.addEdge('C', 'A')

其结果是图形无周期".这显然是错误的. 您能帮我解决这个问题吗?

Its result is 'Graph has no cycle'. This is clearly wrong. Can you help me to solve this problem?

推荐答案

问题是在[1]中给出的示例:

The issue is the example given at [1]: https://www.geeksforgeeks.org/detect-cycle-in-a-graph/ works for integers only because they use the range() function to create a list of nodes,see the line

for node in range(self.V):

这使得不仅所有节点都是整数，而且它们都将是连续集，即[0,1,2,3]可以，而[0,3,10]则不是.

That makes the assumption that not only will all the nodes be integers but also that they will be a contiguous set i.e. [0,1,2,3] is okay but [0,3,10] is not.

如果您想使用任何节点，可以通过将上面给出的行替换为

You can fix the example if you like to work with any nodes by swapping the line given above with

for node in self.graph.keys():

它将遍历所有节点，而不是一系列数字:)

which will loop through all the nodes instead of a range of numbers :)

这篇关于如何使用Python检测有向图中的循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！