从起始节点找到 dag 中每个节点的最长路径

Question

使用修改后的 BFS，如果找到比目前看到的更长的路径，我们可以通过重新访问节点来找到它。对于 ex - D -> G 会将 G 标记为已访问序列 = 3（D 的序列）+ 1 = 4。但是在访问 F -> G 时，会找到一条更长的路径，这将给出 G = 4 的新序列（seq F ) + 1 = 5

最后，如果在hashmap中，在下面的实现中为每个节点保存最后一个序列，可以获得最高的。但这需要重新访问节点。此外，使用 DFS 的拓扑排序在这里不起作用，因为它可能给出这样的顺序和序列 -> A -> C -> E -> F -> B -> D -> G -> H ，但事实上， B & C 应该得到相同的序列，因为它们具有相似的依赖结构。

public void bfsWithLevel(Vertex<T> root)
{
 Queue<Vertex<T>> queue = new LinkedList<>();
 root.setVisited(true);
 queue.add(root);
 root.setSequence(1);
 while (!queue.isEmpty())
 {
 Vertex<T> actualVertex = queue.remove();
 log.info(actualVertex + " ");

 for (Vertex<T> v : actualVertex.getAdjacencyList())
 {
 if (!v.isVisited() || v.getSequence() < actualVertex.getSequence() + 1)
 {
 v.setSequence(actualVertex.getSequence() + 1);
 v.setVisited(true);
 queue.add(v);
 }
 }
 }
}

正在寻找一个避免重访的最佳解决方案，并寻找一个没有任何循环的 dag 的线性时间解决方案。

Answer 1

你面临重访，因为你一发现就推v。相反，您可以推迟它，并且仅在遍历所有传入链接时才推送它，如下所示：

    for (Vertex<T> v : actualVertex.getAdjacencyList())
    {
        if (v.getSequence() < actualVertex.getSequence() + 1)
        {
            v.setSequence(actualVertex.getSequence() + 1);
        }
        v.incoming--;
        if (v.incoming == 0) {
            q.add(v);
        }
    }

当然，要使其正常工作，应对图进行预处理，以计算每个节点的传入链接数。这是另一个（常规）BFS 扫描，但总时间保持线性。

从起始节点找到 dag 中每个节点的最长路径

find longest paths for each node in a dag from start node

algorithm

graph

directed-acyclic-graphs

data-structures