我尝试在包含 26 个节点的最小生成树上执行 DFS。 节点被命名为“A”到“Z”,树是无向的。
我正在尝试编写一个名为 DFS 的空函数,它(我假设)接受树(二维数组)、startNode(随机选择的节点“M”)和 endNode(随机选择的节点“Z')。
连接节点的权重在二维数组参数中标识,但我如何真正开始访问节点?
所需要做的就是按照 DFS 遍历的顺序打印每个节点名称。
我需要为二维数组中的每个节点创建一个 Node_class 吗?
最佳答案
在深度优先搜索中,您只需要确保在返回树以获得下一个分支之前遍历到叶节点的边的整个长度。我不确定我是否理解问题的目标,但我相信您所得到的是正确的。为了跟踪哪个节点被访问以及从起始节点到任何给定节点的总距离/权重是多少,您需要跟踪额外的信息,即它是否已被访问以及每个节点的最低权重是多少。假设您创建一个“包装”类,它将携带这两个额外的信息,默认访问为 false,默认权重为无穷大或某个非常大的数字。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
关于java - 深度优先搜索 - 在树上执行 DFS,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4558912/