我试图在包含 26 个节点的最小生成树上执行 DFS。节点被命名为“A”到“Z”并且树是无向的。
我在这里尝试编写一个名为 DFS 的空函数，它（我假设）在树（一个 2D 数组）中接收一个 startNode（随机选择的节点“M”）和 endNode（随机选择的节点“Z”） .
连接节点的权重在 2D 数组参数中标识，但我如何真正开始访问节点？
所需要的只是按照 DFS 遍历的顺序打印每个 nodeName。
我需要为二维数组中的每个节点创建一个 Node_class 吗？
问问题
1316 次
1 回答
1
在深度优先搜索中，您只需要确保在向上移动到树以获取下一个分支之前，您正在遍历边缘的整个长度到叶节点。我不确定我是否理解问题的目标，但我相信你得到的是正确的。为了跟踪访问了哪个节点以及从起始节点到任何给定节点的总距离/权重是多少，您需要跟踪额外信息，即它是否已被访问以及每个节点的最低权重是多少. 假设您创建了一个“包装器”类，它将携带这两条额外的信息，默认已访问为 false 并将权重默认为无穷大或一些非常大的数字。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
于 2010-12-30T00:31:00.190 回答