广度优先搜索和深度优先搜索旅行商问题

本文介绍了广度优先搜索和深度优先搜索旅行商问题的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

Need help in implementing the Breadth First Search (BFS) and Depth First Search (DFS) algorithms for a Travel Salesman Problem to find and print the shortest path and its total distance of the given 11 cities starting from city 1 to city 11. city x-coordinate y-coordinate 1 5.681818 63.860370 2 11.850649 83.983573 3 13.798701 65.092402 4 16.883117 40.451745 5 23.782468 56.262834 6 25.000000 31.211499 7 29.951299 41.683778 8 31.331169 25.256674 9 37.175325 37.577002 10 39.935065 19.096509 11 46.834416 29.979466

推荐答案

这是我的代码，怎么做我整合了最短路径的距离计算 This is my code, how do I integrate the distance calculation for the shortest path found import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Graph { public Node rootNode; public ArrayList nodes=new ArrayList(); public int[][] adjMatrix;//Edges will be represented as adjacency Matrix int size; public void setRootNode(Node n) { this.rootNode=n; } public Node getRootNode() { return this.rootNode; } public void addNode(Node n) { nodes.add(n); } //This method will be called to make connect two nodes public void connectNode(Node start,Node end) { if(adjMatrix==null) { size=nodes.size(); adjMatrix=new int[size][size]; } int startIndex=nodes.indexOf(start); int endIndex=nodes.indexOf(end); adjMatrix[startIndex][endIndex]=1; adjMatrix[endIndex][startIndex]=1; } private Node getUnvisitedChildNode(Node n) { int index=nodes.indexOf(n); int j=0; while(j<size) { if(adjMatrix[index][j]==1 && ((Node)nodes.get(j)).visited==false) { return (Node)nodes.get(j); } j++; } return null; } //BFS traversal of a tree is performed by the bfs() function public void bfs() { //BFS uses Queue data structure Queue q=new LinkedList(); q.add(this.rootNode); printNode(this.rootNode); rootNode.visited=true; while(!q.isEmpty()) { Node n=(Node)q.remove(); Node child=null; while((child=getUnvisitedChildNode(n))!=null) { child.visited=true; printNode(child); q.add(child); } } //Clear visited property of nodes clearNodes(); } //DFS traversal of a tree is performed by the dfs() function public void dfs() { //DFS uses Stack data structure Stack s=new Stack(); s.push(this.rootNode); rootNode.visited=true; printNode(rootNode); while(!s.isEmpty()) { Node n=(Node)s.peek(); Node child=getUnvisitedChildNode(n); if(child!=null) { child.visited=true; printNode(child); s.push(child); } else { s.pop(); } } //Clear visited property of nodes clearNodes(); } //Utility methods for clearing visited property of node private void clearNodes() { int i=0; while(i<size) { Node n=(Node)nodes.get(i); n.visited=false; i++; } } //Utility methods for printing the node's label private void printNode(Node n) { System.out.print(n.label+" "); } }