/**/ /*
?*?原題如下：用1、2、2、3、4、6這六個數(shù)字，用java寫一個main函數(shù)，打印出所有不同的排列，
?*?如：612234、412346等，要求："4"不能在第三位，"3"與"6"不能相連.?
?*?
?*?1?把問題歸結(jié)為圖結(jié)構(gòu)的遍歷問題。實際上6個數(shù)字就是六個結(jié)點，把六個結(jié)點連接成無向連通圖，對于每一個結(jié)點求這個圖形的遍歷路徑，
?*?所有結(jié)點的遍歷路徑就是最后對這6個數(shù)字的排列組合結(jié)果集。?
?*?2?顯然這個結(jié)果集還未達(dá)到題目的要求。從以下幾個方面考慮：?
?*?1.?3，6不能相連：實際要求這個連通圖的結(jié)點3，5之間不能連通,?可在構(gòu)造圖結(jié)構(gòu)時就滿足改條件，然后再遍歷圖。?
?*?2.?不能有重復(fù):?考慮到有兩個2，明顯會存在重復(fù)結(jié)果，可以把結(jié)果集放在TreeSet中過濾重復(fù)結(jié)果?
?*?3.?4不能在第三位:?仍舊在結(jié)果集中去除滿足此條件的結(jié)果。
? */

import ?java.util.Iterator;
import ?java.util.TreeSet;

public ? class ?Test? {

? private ?String[]?b? = ? new ?String[]? {? " 1 " ,? " 2 " ,? " 2 " ,? " 3 " ,? " 4 " ,? " 6 " ?} ;

? private ? int ?n? = ?b.length;

? private ? boolean []?visited? = ? new ? boolean [n];

? private ? int [][]?a? = ? new ? int [n][n];

? private ?String?result? = ? "" ;

? private ?TreeSet?set? = ? new ?TreeSet();

? public ? static ? void ?main(String[]?args)? {
?? new ?Test().start();
?}

? private ? void ?start()? {

?? // ?Initial?the?map?a[][]
?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {
??? for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {
???? if ?(i? == ?j)? {
?????a[i][j]? = ? 0 ;
????} ? else ? {
?????a[i][j]? = ? 1 ;
????}
???}
??}

?? // ?3?and?5?can?not?be?the?neighbor.
??a[ 3 ][ 5 ]? = ? 0 ;
??a[ 5 ][ 3 ]? = ? 0 ;

?? // ?Begin?to?depth?search.
?? for ?( int ?i? = ? 0 ;?i? < ?n;?i ++ )? {
??? this .depthFirstSearch(i);
??}

?? // ?Print?result?treeset.
??Iterator?it? = ?set.iterator();
?? while ?(it.hasNext())? {
???String?string? = ?(String)?it.next();
???System.out.println(string);
??}
?}

? private ? void ?depthFirstSearch( int ?startIndex)? {
??visited[startIndex]? = ? true ;
??result? = ?result? + ?b[startIndex];
?? if ?(result.length()? == ?n)? {
// ???"4"?can?not?be?the?third?position.
??? if ?(result.indexOf( " 4 " )? != ? 2 )? {
// ????Filt?the?duplicate?value.
????set.add(result);
???}
??}
?? for ?( int ?j? = ? 0 ;?j? < ?n;?j ++ )? {
??? if ?(a[startIndex][j]? == ? 1 ? && ?visited[j]? == ? false )? {
????depthFirstSearch(j);
???}
??}

?? // ?restore?the?result?value?and?visited?value?after?listing?a?node.
??result? = ?result.substring( 0 ,?result.length()? - ? 1 );
??visited[startIndex]? = ? false ;
?}
}

只要這樣定義圖，根本不用在代碼中寫IF ELSE語句。
實際上基于圖的算法好處在于，只要你能定義好滿足題目要求的圖結(jié)構(gòu)，遍歷的結(jié)果就是你要的結(jié)果，不用任何對遍歷結(jié)果做任何處理。包括本題中的：4不能在第三位置，3，5不能相連，唯一性要求，其實都可以在體現(xiàn)在構(gòu)造的圖形結(jié)構(gòu)里，然后直接遍歷圖取得自己要的結(jié)果。而不用再次處理結(jié)果集。只是說這里實際上對其它要求要體現(xiàn)在圖結(jié)構(gòu)里有困難（理論上是可以的），但起碼3，5不能相接是很好構(gòu)造的，就是上面的代碼段來解釋的。

關(guān)于圖形數(shù)據(jù)結(jié)構(gòu)建議先看看數(shù)據(jù)結(jié)構(gòu)的書，主要是將如何利用二維數(shù)組描述圖結(jié)構(gòu)，再看看圖的深度遍歷實現(xiàn)原理。最后再應(yīng)用到這個問題上來，自然就不難明白了。