有向循环图的最长路径 [英] Longest Path for Directed Cyclic Graph

问题描述

使用什么算法通过定向循环未加权图找到最长路径。每个节点只指向另一个节点。这些图表最多有10 ^ 9个节点。 （我在这里搜索和谷歌无济于事。）

解决方案

所以你没有一个单一的图形，而是一系列如果是这样的话，你可以实现一个粗略使用 O的算法（n）时间复杂度和 O（n）空间复杂度（假定随机访问所有节点并且每个节点具有升序ID） / p>

从第一个节点开始，遍历链，直到返回第一个节点。对于每个访问节点，用链标识符标记它。存储此链ID的访问节点数。然后你去到下一个节点（通过ID，而不是在链中），检查它是否已经被标记为链的一部分。如果是，继续前进;如果没有，处理链。做到这一点，直到你在最后一个节点ID。在这一点上，你已经完成了，你知道所有链条的长度，然后你选择最长的链条。

What algorithm is used to find the longest path thru a directed cyclic unweighted graph. Each node points to only one other node. The graphs have up to 10^9 nodes. (I searched here and google to no avail.)

解决方案

So you don't have one single graph but rather a series of distinct graphs which each form a closed chain with various number of nodes.

If that is the case, you can implement an algorithm which roughly uses O(n) time complexity and O(n) space complexity (assuming random access to all nodes and that each node has an ascending ID).

Start at the first node, and traverse the chain until you are back on the first node. For each visited node, mark it with a chain identifier. Store the number of visited nodes for this chain ID. Then you go to the next node (by ID, not in the chain), check if it has already been marked as being part of a chain. If yes, move on; if not, process the chain. Do that until you're on the last node ID. At this point you're done and you know the length of all chains, and then you pick the longest one.

这篇关于有向循环图的最长路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！