如何将最小生成树转换为 Java 中的 path/route？

Question

我在 Java 中有一个最小生成树。
这是在一个 Graph class 中，它有一个 Node 的列表，那些 Node class 有一个 Edge [=25 的列表=]如果它们在 MST 中则有一个布尔值。
示例：

在这个例子中，一个人可以看到一个 path/route 去所有的地方然后从头开始是：（Start-A --> A-Start --> Start-B --> B-C --> C-B --> B-D --> D-B --> B-Start)，我如何将这条路由编码为字符串，只知道使用哪些连接和开始？

Answer 1

这个问题可以用树的 DFS 来解决。
使用 Start 作为根来查看树可能很有用。
想象一下，我们从节点 Start 转到节点 A。我们将此动作添加到我们的 path 字符串中。现在有两种可能性可以实现：第一种是A没有child，所以我们回到Start，我们必须打印之前完成的运动的逆过程；第二个是 A 有一个或多个 children，在这种情况下，我们进行移动以到达第一个 child（更新字符串）。当我们探索完这个 child 的“深度”后，我们将返回 A 并从另一个 child（如果存在）开始。

可能用文字解释比在代码中看到更难：这里的 关键概念 是当我们完成探索可能路径的深度时，我们必须回到节点它从哪里开始（仅对应于在 parent 中添加移动字符串的倒数）。

public void dfs(Node u, Node previous, StringBuilder path) {
        for(Edge e: u.edges) {
            // an edge is a pair (e.a, e.b)
            if(!e.mst || e.b.equals(previous)) {
                continue;
            }
            path.append(u + "->" + e.b + "\n");
            dfs(e.b, u, path);
            path.append(e.b + "->" + u + "\n"); // after exploring a child we must get back
        }
    }

这是您可以根据您的用例进行调整的代码示例。

如何将最小生成树转换为 Java 中的 path/route？

How to convert a minimum spanning tree to a path/route in Java?

java

minimum-spanning-tree

data-structures