使用什么算法来找到通过有向循环未加权图的最长路径。每个节点仅指向一个其他节点。这些图最多有 10^9 个节点。 (我在这里搜索和谷歌都无济于事。)
最佳答案
因此您没有一个单一的图，而是一系列不同的图，每个图形成一个具有不同数量节点的闭合链。
如果是这种情况，您可以实现一个大致使用 O(n) 时间复杂度和 O(n) 空间复杂度的算法(假设随机访问所有节点，每个节点都有一个升序 ID)。
从第一个节点开始，遍历链，直到回到第一个节点。对于每个访问过的节点，用链标识符标记它。存储此链 ID 的已访问节点数。然后你转到下一个节点(通过 ID，不在链中)，检查它是否已经被标记为链的一部分。如果是，继续；如果没有，处理链。这样做直到您到达最后一个节点 ID。此时你就大功告成了，你知道所有链的长度，然后你选择最长的一个。
关于algorithm - 有向循环图的最长路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41097905/