java - 找出图的最大长度

Question

我需要你的帮助来解决一个问题。这是编码练习的一部分，我无法完全解决。

假设我们有以下图表:

我需要构建一个类来计算路径的最大长度。我没有根，必须使用每个顶点作为起点。该方法有一个最大重复次数的参数，所以如果是 1，我们可以只通过每条边一次，如果是 2，我们可以通过一个每个边最多 2 次。

在这种情况下，如果repeats=1，最大路径应该是(B,A,C)。它repeats=2，那么最大路径应该是(B, A, B, A, C, C)。

为了不重复地解决这个问题，我想到了建立一个邻接表并运行一个DFS来找到图中所有的路径并提取最大的一个。我认为这应该适用于更简单的情况。

但我不知道当我们可以重复边缘时该怎么做。我可以用什么样的算法来解决这个问题。您还能想出更有效的方法来解决这个问题吗？

谢谢

Answer 1

您可以使用深度优先搜索的修改版本。

在这种情况下，您不仅将节点标记为已访问，还向它们添加了一些卫星数据:已访问的次数以及何时达到repeats 您将它们标记为已访问。

来自维基百科的修改后的伪代码:

procedure DFS(G,v):
    increment v.timesVisited
    for all edges e in G.adjacentEdges(v) do
        if edge e.timesVisited < repeats then
            w ← G.adjacentVertex(v,e)
            if vertex w.timesVisited < repeats then
                e.timesVisited++
                recursively call DFS(G,w)
            else
                label e as a back edge

我希望它能工作我没有测试修改。