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

问题描述

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

推荐答案

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+" ");
	}





}

这篇关于广度优先搜索和深度优先搜索旅行商问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！