相关疑难解决方法(0)

给定具有n个顶点(| V | = n)的无向图G =(V,E),如何找到它是否包含O(n)中的循环？

我正在寻找一种简单的算法来"序列化"有向图.特别是我有一组在执行顺序上具有相互依赖性的文件,我想在编译时找到正确的顺序.我知道它必须是一件相当普遍的事情 - 编译器会一直这样做 - 但我的google-fu今天一直很弱.什么是'go-to'算法？

我们如何检测有向图是否是循环的？我认为使用广度优先搜索,但我不确定.有任何想法吗？

可能重复:
查找链接列表中是否存在没有两个指针的循环
如何确定链接列表是否只使用两个内存位置进行循环.
测试链表是否有循环的最佳算法

在准备面试时,我遇到了以下问题:

如何使用额外的空间复杂度O(1)来确定链接列表(任何类型)是否包含循环？您不能假设循环从第一个节点开始(当然,循环不必包含所有节点).

我找不到答案,虽然我觉得这很简单......

对于无向图,如果我们需要找到一个循环,我们使用深度优先搜索,如这个较老的问题所述,这是一个众所周知的方法,也是最优的.

但对于有向图,另一个问题建议使用拓扑排序.

我的问题是,为什么我们不能使用我们用于无向图的相同技术来检查有向图中的周期？我已经想到了各种情况,算法似乎总是同意.

任何人都可以提出一些示例有向图,其中DFS无法找到一个循环,但拓扑排序呢？

我想检查 JavaScript 中的图是否是循环的。我有两个数组，第一个数组中的每个项目与第二个数组的（相同索引）项目有关系。

我们举个例子：first = [4, 2, 3, 1] second = [2, 3, 1, 4]

因此，4=>2、2=>3、3=>1 和 1=4 之间存在关系。当您查看该图时，您会发现它是循环的。

我编写了这段代码，但它正在返回，false尽管它应该返回true以下输入；

first = [2, 1, 3, 4] second = [3, 2, 1, 3]

我怎样才能实现这个目标？我需要使用图算法吗？

function ifGraphCyclic(first, second) {
    let nodes = new Map();
    let unique = [];
    for (let i = 0; i < first.length; i++) {
        nodes.set(first[i], second[i]);
    }

    for (let value of nodes.values()) {
        unique.push(nodes.get(value));
    }

    if (first.length === new Set(unique).size) {
        return true; …

我有一个像一些输入：[('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')

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