java实现哈密顿路径，递归和非递归两种方式

导入eclipse就可以使用，用两种方式实现了寻找哈密顿路径。

package com.hmt;

import java.util.Date;

/**
 * @date 2017年4月13日 下午3:18:43
 *
 * @author zhaol
 *
 * @Description 哈密顿 递归 
 */
public class HamiltonPath1 {
	private static int len;//图的顶点的个数
	private static int[] path;//存储哈密顿路径的一维数组
	private static int count = 0;//所有的哈密顿的路径的个数
	/**
	 * @date 2017年4月12日 下午3:38:53
	 *
	 * @author zhaol
	 *
	 * @Description  列出所有的哈密断路径
	 *
	 */
	public void allHamiltonPath（int[][] x）{
		len = x.length;
		path = new int[len];
		int i;
		for （i = 0; i < len; i++） { // Go through column（of matrix）
			path[0] = i + 1;
			findHamiltonpath（x 0 i 0）;
		}
	}
	
	/**
	 * @date 2017年4月12日 下午3:40:50
	 *
	 * @author zhaol
	 *
	 * @Description 指定起点和终点（-1为不指定），寻找所有的哈密断路径
	 */
	public void SpecHamiltonPath（int[][] x int startP） {
		len = x.length;
		path = new int[len];
		path[0] = startP;
		findHamiltonpath（x 0 startP-1 0）;
	}

	/**
	 * @date 2017年4月12日 下午3:41:46
	 *
	 * @author Paul editBy zhaol
	 *
	 * @Description 寻找哈密顿路径的主算法
	 */
	private void findHamiltonpath（int[][] M int x int y int l） {
		int i;
		for（i = x; i < len; i++） { // Go through row
			if（M[i][y] != 0） { // 2 point connect
				if（detect（path i + 1））// if detect a point that already in the path => duplicate
					continue;
				l++; // Increase path length due to 1 new point is connected
				path[l] = i + 1; // correspond to the array that start at 0 graph that start at point 1
				if （l == len - 1） {// Except initial point already count =>success connect all point
					count++;
	                    if （count == 1）
	                        System.out.println（“Hamilton path of graph: “）;
					display（path）;
					l--;
					continue;
				}
				M[i][y] = M[y][i] = 0; // remove the path that has been get and
				findHamiltonpath（M 0 i l）; // recursively start to find new path at new end point
				l--; // reduce path length due to the failure to find new path
				M[i][y] = M[y][i] = 1; // and tranform back to the inital form of adjacent matrix（graph）
			}
		}
		path[l + 1] = 0; // disconnect two point correspond the failure to find the possible hamilton path at new point（ignore newest point try another one）
	}
	/**
	 * @date 2017年4月12日 下午3:42:52
	 *
	 * @author zhaol
	 *
	 * @Description 根据不同的配置输出哈密顿路径
	 */
	public void display（int[] x） {
		System.out.print（count + “ : “）;
        for （int i : x） {
            System.out.print（i + “ “）;
        }
        System.out.println（）;
	}
	/**
	 * @date 2017年4月12日 下午3:43:31
	 *
	 * @author zhaol
	 *
	 * @Description 检测path中是否有重复的点
	 */
	private boolean detect（int[] x int target） {
		boolean t = false;
		for （int i : x） {
			if （i == target） {
				t = true;
				break;
			}
		}
		return t;
	}
	
	/**
	 * @date 2017年4月12日 下午3:45:55
	 *
	 * @author zhaol
	 *
	 * @Description 测试代码 
	 */
	public static void main（String[] args） {
		long startTime = new Date（）.getTime（）;
		HamiltonPath1 obj = new HamiltonPath1

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        301  2017-04-13 15:13  HMT\.classpath

     文件        379  2017-04-13 15:13  HMT\.project

     文件        598  2017-04-13 15:13  HMT\.settings\org.eclipse.jdt.core.prefs

     文件       2834  2017-04-13 15:19  HMT\bin\com\hmt\HamiltonPath1.class

     文件       3635  2017-04-13 15:22  HMT\bin\com\hmt\HamiltonPath2.class

     文件       3877  2017-04-13 15:19  HMT\src\com\hmt\HamiltonPath1.java

     文件       3157  2017-04-13 15:22  HMT\src\com\hmt\HamiltonPath2.java

     目录          0  2017-04-13 15:19  HMT\bin\com\hmt

     目录          0  2017-04-13 15:19  HMT\src\com\hmt

     目录          0  2017-04-13 15:13  HMT\bin\com

     目录          0  2017-04-13 15:13  HMT\src\com

     目录          0  2017-04-13 15:13  HMT\.settings

     目录          0  2017-04-13 15:13  HMT\bin

     目录          0  2017-04-13 15:13  HMT\src

     目录          0  2017-04-13 15:13  HMT

----------- ---------  ---------- -----  ----

                14781                    15