如何在图中找到最长路径？
我们得到了表格的邻接列表
U -> (U,V,C) -> (U,V,C) ...
U2 -> ...
U3 -> ...
.
.
etc
（U，V，C）意味着从U到V有一个成本C的优势。
给定的邻接列表适用于具有N个节点的单连通树，因此包含N-1条边。
给出了一组节点F=F1、F2、F3…Fk。
现在的问题是，在F中的节点中找到最长路径的最佳方法是什么？可以用O（N）来做吗？
来自F中每个节点的DFS是唯一的选项吗？
共有2个答案
如果我正确理解了你的问题，你正试图在生成树中找到最长的成本路径。
对于N的大值，只需2次完全遍历即可找到路径，即O（2N）~O（N）。
您应该执行以下步骤。
- 选择生成树中的任意节点
这将不是您通过随机选取节点开始的最长成本路径。
您不必从每个节点运行DFS。
我理解你的问题是要求从集合F中找到一对节点，以便这两个节点之间的唯一路径尽可能长。路径是唯一的，因为图形是树。
这个问题可以通过从F中的每个节点执行DFS来解决，正如您所提到的，对于O（nk）解决方案，其中n是图的大小，k是集合F的大小。
但是，您可以通过分而治之的方法更快地解决它。从图中选取任意节点R，并使用单个DFS将距离Dist（R，a）列成表格，与每个其他节点a，同时将节点划分为子树S1，…，Sm，其中m是距离R的边数；也就是说，这些是挂在根R上的m棵树。现在，对于属于不同子树的任何f和g，它认为它们之间的路径有Dist（R，f）Dist（R，g）边，因此可以在O（k^2）时间内搜索最长的路径。此外，您还必须递归到子问题S1，…，Sm，以覆盖最长路径位于其中一棵树内的情况。总体复杂度可以低于O（nk），但数学问题留给读者作为练习。
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
我是OGDF库的新手，需要在无环有向图中找到最长的路径（我想使用函数中内置的OGDF）。我知道，用负权值的最短路径算法可以找到最长的路径，但也找不到合适的函数。OGDF是否有特定的功能来做到这一点？如果是，我如何使用它？
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：
-
我已经用两个类实现了一个DS Trie:Trie和TrieNode。我需要编写一个函数，返回在O(h)中Trie中最长的字符串。我的TrieNode有一个字段LinkedList，它存储每个节点的子节点。我们还没有了解到BFS或DFS，所以我正在努力思考一些创造性的方法来解决它。 我已经有了一个函数（一个单独的函数），它通过给定的char插入/创建一个新节点：在构建trie时：创建一个节点，该节点
-
如果我正确地看到了这一点，那么trie中的所有叶节点都将拼写出整个单词，所有父节点都包含最终叶节点之前的字符。因此，如果我有一个名为DigitalTreeNode的类，其定义为 如果我想实现一个返回trie中最长单词的方法，是否只需要在每个叶节点查找最长单词？如何实现方法，例如： 我猜它涉及到设置一个最长的字符串变量，递归地遍历每个节点，并检查它是否是一个单词，如果它是一个单词，并且它的长度大于最
-
我正在尝试解决在图表中查找最长路径的问题。即使在维基百科中，它也提到我们正试图找到最长的简单路径 。 简单路径是没有顶点/边重复的路径。 非简单路径是顶点/边可以重复的路径。我可以把循环或者回路看作非简单路径。而且由于电路总是有循环的。 问题： 对于有向/无向图，我可以这样说。非简单路径总是有循环吗 因为在非简单路径中有一个循环，最长的非简单路径或图是不可能的？（就像我们没有找到负边图的最短距离的