开发者

java - Depth First Search - Perform DFS on a tree

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 weight开发者_开发百科s 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??


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

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜