时间戳

首页 > 解决方案 > 从起始节点查找 dag 中每个节点的最长路径

algorithm - 从起始节点查找 dag 中每个节点的最长路径

问题描述

在此处输入图像描述

使用修改后的 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 的线性时间解决方案。

标签： algorithmdata-structuresgraphdirected-acyclic-graphs

解决方案

你面临重访，因为你一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 扫描，但总时间保持线性。

推荐阅读