加权无向邻接表：O(n) 中单个循环中的最大加权边

Question

所以这个问题涉及一个基于AdjacencyList的图G。这个图恰好有n条边和n个顶点。它也有一个，而且只有一个循环。找到循环中具有最大权重的边缘的最快算法（就大 O 符号而言）是什么？

我很确定这可以在 O(n) 内完成，但考虑到您必须验证您的结果是否在一个循环中，我正在努力弄清楚具体细节。我最初思考这个问题的方法是简单的深度优先搜索，你可以用它在 O(n) 时间内找到整个图中的最大加权边（因为 V+E = 2n）。然后您可以进行另一次搜索以验证该边缘是否在循环中。如果是，那么你在 O(n) 中得到答案，但如果不是，则需要 O(n^2) 时间。这绝对不是理想的，我正在寻找 O(n) 解决方案。

Answer 1

您可以 return 在 DFS 中找到循环中的哪个节点，然后返回将 DFS 树中的每个节点标记为循环的一部分（直到找到节点本身）。像这样：

DFS(v):
    mark v as visited
    for edges (v, w) in E:
        if w is not visited:
             last_node = DFS(w)
             if last_node != -1:
                  test (v, w) as maximum edge
                  if last_node != v:
                      return last_node
                  else:
                      return -1       
        else:
             test (v, w) as maximum edge
             return w  
    return -1

加权无向邻接表：O(n) 中单个循环中的最大加权边

Weighted, Undirected Adjacency List: Maximum Weighted Edge in a Single Cycle in O(n)

algorithm

graph

depth-first-search