我最近一直在开发一个类来查看给定的无向图有一个哈密顿循环。我发现了这篇有趣的文章
http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/。
我已经相应地开发了我的代码。但问题是算法无法返回哈密尔顿循环。
图.java：
package graph;
public class Graph {
private static Map<String, Vertex> vertices = new HashMap<String, Vertex> ();
public static Map<String, LinkedList<Edges>> vertexs = new HashMap<String, LinkedList<Edges>>();
private static Vector<Vertex> verticesID =new Vector<Vertex>();
private static Vector<String> verticesIDString =new Vector<String>();
public Graph(String fileName) {
// TODO Auto-generated constructor stub
this.LoadGraph(fileName);
}
public int addVertex(String ID){
if (vertices.containsKey(ID))
return -1;
Vertex vertex=new Vertex(ID);
vertices.put(ID, vertex);
LinkedList<Edges> node =new LinkedList<Edges>();
vertexs.put(ID, node);
return 1;
}
public int addEdge(String from, String to, double weight){
//check whether the vertices exist or not
if (vertices.containsKey(from) && vertices.containsKey(to)){
vertices.get(from).addEdge(to, weight);
Edges newEdge = new Edges(from,to,weight);
if(vertexs.get(from) == null)
{
vertexs.put(from, new LinkedList<Edges>());
}
vertexs.get(from).add(newEdge);
return 1;
}
else{
System.err.println ("'From' vertex and/or 'to' vertex dosen't exist! ");
return -1;
}
}
private int LoadGraph(String fileName) {
File f;
BufferedReader in;
try {
f = new File(fileName);
in = new BufferedReader(new FileReader(f));
String delim = "[ ]+";
//String delim = "\t";
String from; String to;double weight;
int cnt = 0;
String line = in.readLine();
//System.out.println(line);
while (line != null) {
//String[] tokens=line.split(delim);
String[] tokens=line.split(delim,-1);
//if there're less than three entries (from,to, weight) then report err
if (tokens.length<3){
System.err.println ("Invalid line format. Line should be formated as: from to weight");
in.close();
return -1;
}
from=tokens[0];
to=tokens[1];
weight=Double.parseDouble(tokens[2]);
//first create the "from" vertex if it's not already created
this.addVertex(from);
//Then create the "to" vertex if it's not already created
this.addVertex(to);
//now associate the "from" vertex with "to" vertex using "weight"
this.addEdge(from, to,weight);
//do the association the other way around, i.e. force graph to be undirected.
this.addEdge(to, from,weight);
//if the "from" vertex is a new one, add it to the key vector
if (!verticesIDString.contains(from)) {
verticesIDString.add(from);
verticesID.add(new Vertex(from));
}
//if the "to" vertex is a new one, add it to the key vector
if (!verticesIDString.contains(to)) {
verticesIDString.add(to);
verticesID.add(new Vertex(to));
}
cnt++;
line = in.readLine();
//System.out.println(line);
}
in.close();
System.out.println(vertices.size());
System.out.println("Successfully added "+cnt+" associations");
return cnt;
} catch (IOException exc) {
System.err.println(exc.toString());
return -1;
}
}
public static ArrayList<Edges> getChildNodes(String node)
{
LinkedList<Edges> neighboursList;
Set<String> keys = vertexs.keySet();
for (String key : keys)
{
if (key.equals(node))
{
neighboursList = vertexs.get(key);
return new ArrayList<Edges>(neighboursList);
}
}
return new ArrayList<Edges>();
}
public Vertex getVertex(String ID){
return vertices.get(ID);
}
public static int getVerticesCount(){
return verticesID.size();
}
public static Vertex getVertexIdByIndex(int idx){
return verticesID.elementAt(idx);
}
public Vector<String> BFS(String start){
//Vector<String> tour = new Vector<String>();
Vector<String> visited = new Vector<String>();
LinkedList<String> queue = new LinkedList<String>();
visited.add(start);
queue.add(start);
while(queue.size() != 0){
String s = queue.poll();
//tour.add(s);
ArrayList<Edges> al = getChildNodes(s);
Iterator<Edges> i = al.listIterator();
while (i.hasNext())
{
String n = i.next().toVertex();
if (!visited.contains(n))
{
visited.add(n);
queue.add(n);
}
}
}
return visited;
}
}
Hamiltoninan.java：
package graph;
public class HamiltonianCycle {
public Vector<String> findHamiltonianCycle(Graph g,String start){
Vector<String> allVertex = g.BFS(start); //this will help us with all the vertices in the graph
Vector<String> path = new Vector<String>(); // To store the hamiltonian path
/*Initialize the path with null at first*/
for(int i=0;i < allVertex.size();i++){
path.add(null);
}
path.add(start); // add the start as the first vertex of the hamiltonian path
/**
*now the recursive functions
*cycle problem
**/
if (hamCycleUtil(g, path,allVertex) == false)
{
System.out.println("\nSolution does not exist");
return null;
}
return path;
}
//The utility function tha recursively finds the hamiltonian cycle
private boolean hamCycleUtil(Graph g, Vector<String> path,Vector<String> vers) {
// TODO Auto-generated method stub
if(path.size() == Graph.getVerticesCount()){
String s1 = path.lastElement();
ArrayList<Edges> LastNodeEdges = Graph.getChildNodes(s1);
for(Edges Node : LastNodeEdges){
if(Node.toVertex().equals(path.firstElement())){
System.out.println(path);
return true;
}
}
return false;
}
for(int i=1;i<vers.size();i++){
if(isSafe(vers.elementAt(i),g,path)){
path.add(vers.elementAt(i));
if(hamCycleUtil(g, path, vers) == true){
return true;
}
}
}
return false;
}
private boolean isSafe(String elementAt, Graph g, Vector<String> path) {
// TODO Auto-generated method stub
if(path.contains(elementAt)){
return false;
}
return true;
}
}
有人可以指出问题出在哪里以及如何解决问题。
谢谢，卡尔蒂。