java - 深度优先搜索 - 在树上执行 DFS

发布于 2024-10-09 19:35:39 字数 274 浏览 1 评论 0原文

我尝试在包含 26 个节点的最小生成树上执行 DFS。 节点被命名为“A”到“Z”,并且树是无向的。

我在这里有一个名为 DFS 的空函数,我正在尝试编写它,它(我假设)接受树(2D 数组)、startNode(随机选择的节点“M”)和 endNode(随机选择的节点“Z”) 。

连接节点的权重在二维数组参数中标识,但我如何真正开始访问节点呢?

所需要做的就是按照 DFS 遍历的顺序打印每个节点名称。

我需要为二维数组中的每个节点创建一个 Node_class 吗?

Im trying to perform DFS on a Minimum Spanning Tree which contains 26 nodes.
Nodes are named 'A' to 'Z' and the tree is undirected.

I have an empty function called DFS here that I am trying to write, which (i presume) takes in the tree (a 2D array) a startNode (randomly selected node 'M') and the endNode (randomly selected node 'Z').

The weights of connected nodes are identified in the 2D array parameter, but how do I actually get started visiting nodes?

All that is required is to print each nodeName in the order of the DFS traversal.

Do I need to create a Node_class for each node in the 2d array??

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

可是我不能没有你 2024-10-16 19:35:39

在深度优先搜索中,您只需要确保在返回树以获得下一个分支之前遍历到叶节点的边的整个长度。我不确定我是否理解问题的目标,但我相信您所得到的是正确的。为了跟踪哪个节点被访问以及从起始节点到任何给定节点的总距离/权重是多少,您需要跟踪额外的信息,即它是否已被访问以及每个节点的最低权重是多少。假设您创建一个“包装”类,它将携带这两个额外的信息,默认访问为 false,默认权重为无穷大或某个非常大的数字。 http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

In depth first search you just need to be sure you're traversing the entire length of an edge to a leaf node before moving back up the tree to get the next branch. I'm not sure I understand the goal of the problem but I believe what you're getting at is correct. In order to track which node is visited and what the total distance/weight to any given node is from the start node you need to keep track of extra information namely if it has been visited or not yet and what the lowest weight to each node is. Assuming you make a "wrapper" class which will carry these two extra pieces of information, default the visited to false and default the weight to infinity or some very large number. http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文