package?com.hmt;

import?java.util.Date;

/**
?*?@date?2017年4月13日?下午3:18:43
?*
?*?@author?zhaol
?*
?*?@Description?哈密頓?遞歸?
?*/
public?class?HamiltonPath1?{
	private?static?int?len;//圖的頂點(diǎn)的個(gè)數(shù)
	private?static?int[]?path;//存儲(chǔ)哈密頓路徑的一維數(shù)組
	private?static?int?count?=?0;//所有的哈密頓的路徑的個(gè)數(shù)
	/**
	?*?@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?			path[0]?=?i?+?1;
			findHamiltonpath（x?0?i?0）;
		}
	}
	
	/**
	?*?@date?2017年4月12日?下午3:40:50
	?*
	?*?@author?zhaol
	?*
	?*?@Description?指定起點(diǎn)和終點(diǎn)（-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?			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?根據(jù)不同的配置輸出哈密頓路徑
	?*/
	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?檢測(cè)path中是否有重復(fù)的點(diǎn)
	?*/
	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?測(cè)試代碼?
	?*/
	public?static?void?main（String[]?args）?{
		long?startTime?=?new?Date（）.getTime（）;
		HamiltonPath1?obj?=?new?HamiltonPath1

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件????????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