3

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

想象一下，我们有以下图表：

在此处输入图像描述

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

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

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

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

谢谢

4

3 回答 3

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

我希望它有效我没有测试修改。

于 2013-05-29T08:58:29.320 回答
0

如果我理解正确，两种情况的解决方案都是相似的。

对于没有重复的解决方案：您将每个节点作为 root ，并在其子节点上启动 DFS。节点的有效子节点是尚未访问的节点。

对于 N 次重复问题：有效子节点是访问次数少于 N 次的节点。在 DFS 中的每次访问中，您都需要更新该节点的访问计数器。另外，当您完成对特定节点的子节点的探索时，您需要将其访问计数器归零。

于 2013-05-29T09:00:54.503 回答
0

我可以看到一种天真的方法。这不是效率，但它有效。

两个要素：

  • 每个边的条目设置为 0 的 Hashmap
  • 使用 DFS 获取图形（递增和递减 hashmap 以了解您的获取）

由于您没有根，我认为您必须为每个节点执行此操作。

您需要找到所有解决方案还是正在寻找一个可行的解决方案？

您在维基百科上找不到关于此类问题的更多解释： http ://en.wikipedia.org/wiki/Longest_path_problem

于 2013-05-29T09:03:01.790 回答