algorithm - 有序图伪代码中的最长路径

Question

我尝试创建一种算法来找到有序图中的最长路径。有序图的属性是：

• 每条边从索引较低的节点到索引较高的节点。也就是说，每条有向边都具有 i < j 的 (v_i, v_j) 形式。
• 除了 v_n 之外的每个节点都至少有一条边离开它。也就是说，对于每个节点 v_i，至少有一个形式为 (v_i, v_j) 的边。

我的第一次尝试如下：

set w = v1 and L = 0
While there is edge that leaves from w
    Choose the edge (w, vj) with j as small as possible
    set w = vj and L = L + 1
return L

我不明白为什么这个算法在某些情况下是错误的。你可以给我一个例子吗？

标签： algorithmgraphpseudocodegreedy

Answer 1

我的直觉告诉我，只选择最小的j并不意味着在其他地方j将继续是最小的。

假设您有一个图1-> 3和1 -> 5，但是3 -> 9，5 -> 7 -> 9其中 9 是最后一个节点。你的算法会1 -> 3 -> 9比1 -> 5 -> 7 -> 9.

事实上，我不认为你真的可以“挑选”一个分支并继续跟随它到最后并且在任何情况下都是正确的：你必须检查其他分支。

递归方法

这是一种使用简单递归算法的方法，在每个分支处计算路径的长度，然后在有多个分支的节点处返回最长的。

简单的伪代码示例（Python 风格）

class node:
    def longest_path(self):
        if len(self.children) == 0: # No children in this node
            return 1
        child_lengths = []
        for child in self.children:
            child_lengths.append(child.longest_path())
        return max(child_lengths) + 1