相关疑难解决方法(0)

如何检查有向图是否是非循环的？算法如何调用？我很感激参考.

程序的输入是图中的边集.例如,考虑以下简单有向图:

a -> b -> c

该图的边集是

{ (b, c), (a, b) }

因此,将有向图作为一组边,如何确定有向图是否为树？如果它是树,那么树的根节点是什么？

首先,我在看你如何表示这个图,邻接列表/邻接矩阵/其他什么？如何利用您选择的表示来有效地回答上述问题？

编辑1:

有些人正在考虑使用DFS进行循环检测,但问题是从哪个节点启动DFS.由于它是有向图,我们无法从随机节点启动DFS,例如,如果我从顶点'c'开始DFS,它将不会继续进行,因为没有后边缘去任何其他节点.这里的后续问题应该是如何确定这棵树的根源.

我有一个像一些输入：[('A', 'B'),('C', 'D'),('D', 'C'),('C', 'D')]。我想在这个 edgeList 表示的有向图中寻找循环是否存在。

我读了一个讨论：https : //www.geeksforgeeks.org/detect-cycle-in-a-graph/，但是当情况是这样时它有一些错误：

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

它的结果是“图没有循环”。这显然是错误的。你能帮我解决这个问题吗？

什么是一种简单的算法来确定作为邻接矩阵给出的图是否是树？

我最近写了一个快速而肮脏的BFS实现,在有向图中找到钻石.BFS循环看起来像这样:

while toVisit:
    y = toVisit.pop()
    if y in visited: return "Found diamond"
    visited.add(y)
    toVisit.extend(G[y])

(G是图表 - 从节点名称到其邻居列表的字典)

然后是有趣的部分:我认为这list.pop()可能太慢了,所以我运行了一个分析器来比较这个实现的速度和deque.pop - 并得到了一点改进.然后我对它进行了比较y = toVisit[0]; toVisit = toVisit[1:],令我惊讶的是,最后一次实现实际上是最快的.

这有意义吗？是否有任何性能原因可以使用list.pop()而不是显然更快的双线程？