資料結構學習筆記-常用十大算法

目錄

• 二分查找算法(非遞歸)
• • 二分查找算法(非遞歸)介紹
  • 二分查找算法(非遞歸)代碼實作
• 分治算法
• • 分治算法介紹
  • 分治算法的基本步驟
  • 分治算法最佳實踐-漢諾塔
  • 漢諾塔遊戲的代碼實作:
• 動态規劃算法
• • 動态規劃算法介紹
  • 應用場景-背包問題
  • • 思路分析和圖解
    • 圖解分析
    • 代碼實作
• KMP算法
• • KMP算法介紹
  • KMP算法最佳應用-字元串比對問題
  • • 字元串比對問題
    • 思路分析圖解
    • 代碼實作
• 貪心算法
• • 貪心算法介紹
  • 貪心算法最佳應用-集合覆寫
  • • 代碼實作
  • 貪心算法注意事項和細節
• 普裡姆算法
• • 普裡姆算法介紹
  • 普裡姆算法最佳實踐(修路問題)
• 克魯斯卡爾算法
• • 克魯斯卡爾算法介紹
  • 克魯斯卡爾算法圖解說明
  • 代碼實作
• 迪傑斯特拉算法
• • 迪傑斯特拉(Dijkstra)算法介紹
  • 迪傑斯特拉(Dijkstra)算法過程
  • 迪傑斯特拉(Dijkstra)算法最佳應用-最短路徑
• 弗洛伊德算法
• • 弗洛伊德(Floyd)算法介紹
  • 弗洛伊德(Floyd)算法圖解分析
  • 弗洛伊德(Floyd)算法最佳應用-最短路徑
• 馬踏棋盤算法
• • 馬踏棋盤算法介紹和遊戲示範
  • 馬踏棋盤遊戲代碼實作

二分查找算法(非遞歸)

二分查找算法(非遞歸)介紹

1. 前面我們講過了二分查找算法，是使用遞歸的方式，下面我們講解二分查找算法的非遞歸方式
2. 二分查找法隻适用于從有序的數列中進行查找(比如數字和字母等)，将數列排序後再進行查找
3. 二分查找法的運作時間為對數時間O(㏒₂n)，即查找到需要的目标位置最多隻需要㏒₂n步，假設從[0,99]的隊列(100個數，即n=100)中尋到目标數30，則需要查找步數為㏒₂100, 即最多需要查找7次( 2^6 < 100 < 2^7)

二分查找算法(非遞歸)代碼實作

數組 {1,3, 8, 10, 11, 67, 100}, 程式設計實作二分查找， 要求使用非遞歸的方式完成

public class BinarySearchNoRecur {

	public static void main(String[] args) {
		//測試
		int[] arr = {1,3, 8, 10, 11, 67, 100};
		int index = binarySearch(arr, 100);
		System.out.println("index=" + index);//
	}
	
	//二分查找的非遞歸實作
	/**
	 * 
	 * @param arr 待查找的數組, arr是升序排序
	 * @param target 需要查找的數
	 * @return 傳回對應下标，-1表示沒有找到
	 */
	public static int binarySearch(int[] arr, int target) {
		
		int left = 0;
		int right = arr.length - 1;
		while(left <= right) { //說明繼續查找
			int mid = (left + right) / 2;
			if(arr[mid] == target) {
				return mid;
			} else if ( arr[mid] > target) {
				right = mid - 1;//需要向左邊查找
			} else {
				left = mid + 1; //需要向右邊查找
			}
		}
		return -1;
	}
}
           

分治算法

分治算法介紹

1. 分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個複雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最後子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……

2. 分治算法可以求解的一些經典問題

   - 二分搜尋

   - 大整數乘法

   - 棋盤覆寫

   - 合并排序

   - 快速排序

   - 線性時間選擇

   - 最接近點對問題

   - 循環賽日程表

   - 漢諾塔

分治算法的基本步驟

分治法在每一層遞歸上都有三個步驟：

1. 分解：将原問題分解為若幹個規模較小，互相獨立，與原問題形式相同的子問題
2. 解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題
3. 合并：将各個子問題的解合并為原問題的解

分治算法最佳實踐-漢諾塔

漢諾塔遊戲的示範和思路分析:

1. 如果是有一個盤， A->C，如果我們有 n >= 2 情況，我們總是可以看做是兩個盤 1.最下邊的盤 2. 上面的盤
2. 先把最上面的盤 A->B
3. 把最下邊的盤 A->C
4. 把B塔的所有盤 從 B->C

漢諾塔遊戲的代碼實作:

public class Hanoitower {

	public static void main(String[] args) {
		hanoiTower(10, 'A', 'B', 'C');
	}
	
	//漢諾塔的移動的方法
	//使用分治算法
	public static void hanoiTower(int num, char a, char b, char c) {
		//如果隻有一個盤
		if(num == 1) {
			System.out.println("第1個盤從 " + a + "->" + c);
		} else {
			//如果我們有 n >= 2 情況，我們總是可以看做是兩個盤 1.最下邊的一個盤 2. 上面的所有盤
			//1. 先把 最上面的所有盤 A->B， 移動過程會使用到 c
			hanoiTower(num - 1, a, c, b);
			//2. 把最下邊的盤 A->C
			System.out.println("第" + num + "個盤從 " + a + "->" + c);
			//3. 把B塔的所有盤 從 B->C , 移動過程使用到 a塔  
			hanoiTower(num - 1, b, a, c);	
		}
	}
}
           

動态規劃算法

動态規劃算法介紹

1. 動态規劃(Dynamic Programming)算法的核心思想是：将大問題劃分為小問題進行解決，進而一步步擷取最優解的處理算法
2. 動态規劃算法與分治算法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。
3. 與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。 ( 即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解 )
4. 動态規劃可以通過填表的方式來逐漸推進，得到最優解.

應用場景-背包問題

有一個背包，容量為4磅 ， 現有如下物品

思路分析和圖解

1. 要求達到的目标為裝入的背包的總價值最大，并且重量不超出
2. 要求裝入的物品不能重複
3. 背包問題主要是指一個給定容量的背包、若幹具有一定價值和重量的物品，如何選擇物品放入背包使物品的價值最大。其中又分01背包和完全背包(完全背包指的是：每種物品都有無限件可用)
4. 這裡的問題屬于01背包，即每個物品最多放一個。而無限背包可以轉化為01背包。

5. 算法的主要思想，利用動态規劃來解決。每次周遊到的第i個物品，根據w[i]和v[i]來确定是否需要将該物品放入背包中。即對于給定的n個物品，設v[i]、w[i]分别為第i個物品的價值和重量，C為背包的容量。再令v[i][j]表示在前i個物品中能夠裝入容量為j的背包中的最大價值。則我們有下面的結果

   (1) v[i][0]=v[0][j]=0; //表示 填入表 第一行和第一列是0

   (2) 當w[i]> j 時：v[i][j]=v[i-1][j] // 當準備加入新增的商品的容量大于 目前背包的容量時，就直接使用上一個單元格的裝入政策

   (3) 當j>=w[i]時： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

   //當準備加入的新增的商品的容量小于等于目前背包的容量，裝入的方式:

   v[i-1][j]： 就是上一個單元格的裝入的最大值

   v[i] : 表示目前商品的價值

   v[i-1][j-w[i]] ： 裝入i-1商品，到剩餘空間j-w[i]的最大值

   當j>=w[i]時： v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

圖解分析

代碼實作

public class KnapsackProblem {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] w = {1, 4, 3};//物品的重量
		int[] val = {1500, 3000, 2000}; //物品的價值 這裡val[i] 就是前面講的v[i]
		int m = 4; //背包的容量
		int n = val.length; //物品的個數
		
		//建立二維數組，
		//v[i][j] 表示在前i個物品中能夠裝入容量為j的背包中的最大價值
		int[][] v = new int[n+1][m+1];
		//為了記錄放入商品的情況，我們定一個二維數組
		int[][] path = new int[n+1][m+1];
		
		//初始化第一行和第一列, 這裡在本程式中，可以不去處理，因為預設就是0
		for(int i = 0; i < v.length; i++) {
			v[i][0] = 0; //将第一列設定為0
		}
		for(int i=0; i < v[0].length; i++) {
			v[0][i] = 0; //将第一行設定0
		}
		
		
		//根據前面得到公式來動态規劃處理
		for(int i = 1; i < v.length; i++) { //不處理第一行 i是從1開始的
			for(int j=1; j < v[0].length; j++) {//不處理第一列, j是從1開始的
				//公式
				if(w[i-1]> j) { // 因為我們程式i 是從1開始的，是以原來公式中的 w[i] 修改成 w[i-1]
					v[i][j]=v[i-1][j];
				} else {
					//說明:
					//因為我們的i 從1開始的， 是以公式需要調整成
					//v[i][j]=Math.max(v[i-1][j], val[i-1]+v[i-1][j-w[i-1]]);
					//v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
					//為了記錄商品存放到背包的情況，我們不能直接的使用上面的公式，需要使用if-else來展現公式
					if(v[i - 1][j] < val[i - 1] + v[i - 1][j - w[i - 1]]) {
						v[i][j] = val[i - 1] + v[i - 1][j - w[i - 1]];
						//把目前的情況記錄到path
						path[i][j] = 1;
					} else {
						v[i][j] = v[i - 1][j];
					}
				}
			}
		}
		
		//輸出一下v 看看目前的情況
		for(int i =0; i < v.length;i++) {
			for(int j = 0; j < v[i].length;j++) {
				System.out.print(v[i][j] + " ");
			}
			System.out.println();
		}
		
		System.out.println("============================");
		//輸出最後我們是放入的哪些商品
		//周遊path, 這樣輸出會把所有的放入情況都得到, 其實我們隻需要最後的放入
//		for(int i = 0; i < path.length; i++) {
//			for(int j=0; j < path[i].length; j++) {
//				if(path[i][j] == 1) {
//					System.out.printf("第%d個商品放入到背包\n", i);
//				}
//			}
//		}
		//動腦筋
		int i = path.length - 1; //行的最大下标
		int j = path[0].length - 1;  //列的最大下标
		while(i > 0 && j > 0 ) { //從path的最後開始找
			if(path[i][j] == 1) {
				System.out.printf("第%d個商品放入到背包\n", i); 
				j -= w[i-1]; //w[i-1]
			}
			i--;
		}	
	}
}
           

KMP算法

KMP算法介紹

1. KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典算法
2. Knuth-Morris-Pratt 字元串查找算法，簡稱為 “KMP算法”，常用于在一個文本串S内查找一個模式串P 的出現位置，這個算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年聯合發表，故取這3人的姓氏命名此算法.
3. KMP方法算法就利用之前判斷過資訊，通過一個next數組，儲存模式串中前後最長公共子序列的長度，每次回溯時，通過next數組找到，前面比對過的位置，省去了大量的計算時間
4. 參考資料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

KMP算法最佳應用-字元串比對問題

字元串比對問題

1. 有一個字元串 str1= “BBC ABCDAB ABCDABCDABDE”，和一個子串 str2=“ABCDABD”
2. 現在要判斷 str1 是否含有 str2, 如果存在，就傳回第一次出現的位置, 如果沒有，則傳回-1

思路分析圖解

舉例來說，有一個字元串Str1= “BBC ABCDAB ABCDABCDABDE”，判斷，裡面是否包含另一個字元串Str2= “ABCDABD”?

1. 首先， 用Str1的第一個字元和Str2的第一 個字元去比較，不符合，關鍵詞向後移動一位

   

2. 重複第一步，還是不符合，再後移

   

3. 一直重複，直到Str1有一個字元與Str2的第一個字元符合為止

   

4. 接着比較字元串和搜尋詞的下一個字元，還是符合。

   

5. 遇到Str1有一個字元與Str2對應的字元不符合。

   

6. 這時候，想到的是繼續周遊Str1的下一個字元，重複第1步。(其實是很不明智的，因為此時BCD已經比較過了，沒有必要再做重複的工作，一個基本事實是，當空格與D不比對時，你其實知道前面六個字元是”ABCDAB”。KMP算法的想法是，設法利用這個已知資訊，不要把“搜尋位置”移回已經比較過的位置，繼續把它向後移，這樣就提高了效率。)

   

7. 怎麼做到把剛剛重複的步驟省略掉?可以對Str2計算出一張《部分比對表》，這張表的産生在後面介紹。

   

8. 已知空格與D不比對時，前面六個字元“ABCDAB”是比對的。查表可知，最後一個比對字元B對應的“部分比對值”為2，是以按照下面的公式算出向後移動的位數:

   移動位數=已比對的字元數-對應的部分比對值。

   因為6-2等于4，是以将搜尋詞向後移動4位。

9. 因為空格與C不比對，搜尋詞還要繼續往後移。這時，己比對的字元數為2 (”AB”)，對應的”部分比對值”為0。是以，移動位數=2-0, 結果為2，于是将搜尋詞向後移2位。

   

10. 因為空格與A不比對，繼續後移一位。

    

11. 逐位比較，直到發現C與D不比對。于是，移動位數=6-2，繼續将搜尋詞向後移動4位。

    

12. 逐位比較， 直到搜尋詞的最後一位，發現完全比對，于是搜尋完成。如果還要繼續搜尋(即找出全部比對) ，移動位數=7-0， 再将搜尋詞向後移動7位，這裡就不再重複了。

    

13. 介紹《部分比對表》怎麼産生的。先介紹字首，字尾是什麼。

    

“部分比對值”就是”字首”和”字尾”的最長的共有元素的長度。以”ABCDABD”為例

• ”A”的字首和字尾都為空集，共有元素的長度為0;
• ”AB”的字首為[A]，字尾為[B], 共有元素的長度為0;
• “ABC”的字首為[A, AB]，字尾為[BC, C]，共有元素的長度0;
• ”ABCD”的字首為[A. AB, ABC]，字尾為[BCD. CD. D],共有元素的長度為0; .
• ”ABCDA"的字首為[A, AB, ABC, ABCD]，字尾為[BCDA, CDA, DA, A],共有元素為”A”,長度為1:
• ”ABCDAB”的字首為[A, AB, ABC, ABCD, ABCDA],字尾為[BCDAB, CDAB, DAB, AB, B],共有元素為”AB",長度為2:
• ”ABCDABD”的字首為[A, AB, ABC, ABCD, ABCDA, ABCDAB],字尾為[BCDABD, CDABD, DABD, ABD, BD,D]，共有元素的長度為0.

1. ”部分比對”的實質是，有時候，字元串頭部和尾部會有重複。比如“ABCDAB”之中有兩個”AB”，那麼它的”部分比對值”就是2 (”AB”的長度)。搜尋詞移動的時候，第一個”AB”向後移動4位(字元串長度-部分比對值)，就可以來到第二個”AB”的位置。

   

代碼實作

import java.util.Arrays;

public class KMPAlgorithm {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "BBC ABCDAB ABCDABCDABDE";
		String str2 = "ABCDABD";
		//String str2 = "BBC";
		
		int[] next = kmpNext("ABCDABD"); //[0, 1, 2, 0]
		System.out.println("next=" + Arrays.toString(next));
		
		int index = kmpSearch(str1, str2, next);
		System.out.println("index=" + index); // 15了
		
		
	}
	
	//寫出我們的kmp搜尋算法
	/**
	 * 
	 * @param str1 源字元串
	 * @param str2 子串
	 * @param next 部分比對表, 是子串對應的部分比對表
	 * @return 如果是-1就是沒有比對到，否則傳回第一個比對的位置
	 */
	public static int kmpSearch(String str1, String str2, int[] next) {
		//周遊 
		for(int i = 0, j = 0; i < str1.length(); i++) {
			
			//需要處理 str1.charAt(i) ！= str2.charAt(j), 去調整j的大小
			//KMP算法核心點, 可以驗證...
			while( j > 0 && str1.charAt(i) != str2.charAt(j)) {
				j = next[j-1]; 
			}
			
			if(str1.charAt(i) == str2.charAt(j)) {
				j++;
			}			
			if(j == str2.length()) {//找到了 // j = 3 i 
				return i - j + 1;
			}
		}
		return  -1;
	}

	//擷取到一個字元串(子串) 的部分比對值表
	public static  int[] kmpNext(String dest) {
		//建立一個next 數組儲存部分比對值
		int[] next = new int[dest.length()];
		next[0] = 0; //如果字元串是長度為1 部分比對值就是0
		for(int i = 1, j = 0; i < dest.length(); i++) {
			//當dest.charAt(i) != dest.charAt(j) ，我們需要從next[j-1]擷取新的j
			//直到我們發現 有  dest.charAt(i) == dest.charAt(j)成立才退出
			//這時kmp算法的核心點
			while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
				j = next[j-1];
			}
			
			//當dest.charAt(i) == dest.charAt(j) 滿足時，部分比對值就是+1
			if(dest.charAt(i) == dest.charAt(j)) {
				j++;
			}
			next[i] = j;
		}
		return next;
	}
}
           

貪心算法

貪心算法介紹

1. 貪婪算法(貪心算法)是指在對問題進行求解時，在每一步選擇中都采取最好或者最優(即最有利)的選擇，進而希望能夠導緻結果是最好或者最優的算法
2. 貪婪算法所得到的結果不一定是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最優解的結果

貪心算法最佳應用-集合覆寫

1. 假設存在如下表的需要付費的廣播台，以及廣播台信号可以覆寫的地區。 如何選擇最少的廣播台，讓所有的地區都可以接收到信号

   

2. 思路分析:

   1）周遊所有的廣播電台, 找到一個覆寫了最多未覆寫的地區的電台(此電台可能包含一些已覆寫的地區，但沒有關系）

   2）将這個電台加入到一個集合中(比如ArrayList), 想辦法把該電台覆寫的地區在下次比較時去掉。

   3）重複第1步直到覆寫了全部的地區

   

代碼實作

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyAlgorithm {

	public static void main(String[] args) {
		//建立廣播電台,放入到Map
		HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
		//将各個電台放入到broadcasts
		HashSet<String> hashSet1 = new HashSet<String>();
		hashSet1.add("北京");
		hashSet1.add("上海");
		hashSet1.add("天津");
		
		HashSet<String> hashSet2 = new HashSet<String>();
		hashSet2.add("廣州");
		hashSet2.add("北京");
		hashSet2.add("深圳");
		
		HashSet<String> hashSet3 = new HashSet<String>();
		hashSet3.add("成都");
		hashSet3.add("上海");
		hashSet3.add("杭州");
		
		
		HashSet<String> hashSet4 = new HashSet<String>();
		hashSet4.add("上海");
		hashSet4.add("天津");
		
		HashSet<String> hashSet5 = new HashSet<String>();
		hashSet5.add("杭州");
		hashSet5.add("大連");
	
		//加入到map
		broadcasts.put("K1", hashSet1);
		broadcasts.put("K2", hashSet2);
		broadcasts.put("K3", hashSet3);
		broadcasts.put("K4", hashSet4);
		broadcasts.put("K5", hashSet5);
		
		//allAreas 存放所有的地區
		HashSet<String> allAreas = new HashSet<String>();
		allAreas.add("北京");
		allAreas.add("上海");
		allAreas.add("天津");
		allAreas.add("廣州");
		allAreas.add("深圳");
		allAreas.add("成都");
		allAreas.add("杭州");
		allAreas.add("大連");
		
		//建立ArrayList, 存放選擇的電台集合
		ArrayList<String> selects = new ArrayList<String>();
		
		//定義一個臨時的集合， 在周遊的過程中，存放周遊過程中的電台覆寫的地區和目前還沒有覆寫的地區的交集
		HashSet<String> tempSet = new HashSet<String>();
		
		//定義給maxKey ， 儲存在一次周遊過程中，能夠覆寫最大未覆寫的地區對應的電台的key
		//如果maxKey 不為null , 則會加入到 selects
		String maxKey = null;
		while(allAreas.size() != 0) { // 如果allAreas 不為0, 則表示還沒有覆寫到所有的地區
			//每進行一次while,需要
			maxKey = null;
			
			//周遊 broadcasts, 取出對應key
			for(String key : broadcasts.keySet()) {
				//每進行一次for
				tempSet.clear();
				//目前這個key能夠覆寫的地區
				HashSet<String> areas = broadcasts.get(key);
				tempSet.addAll(areas);
				//求出tempSet 和   allAreas 集合的交集, 交集會賦給 tempSet
				tempSet.retainAll(allAreas);
				//如果目前這個集合包含的未覆寫地區的數量，比maxKey指向的集合地區還多
				//就需要重置maxKey
				// tempSet.size() >broadcasts.get(maxKey).size()) 展現出貪心算法的特點,每次都選擇最優的
				if(tempSet.size() > 0 && 
						(maxKey == null || tempSet.size() >broadcasts.get(maxKey).size())){
					maxKey = key;
				}
			}
			//maxKey != null, 就應該将maxKey 加入selects
			if(maxKey != null) {
				selects.add(maxKey);
				//将maxKey指向的廣播電台覆寫的地區，從 allAreas 去掉
				allAreas.removeAll(broadcasts.get(maxKey));
			}	
		}
		System.out.println("得到的選擇結果是" + selects);//[K1,K2,K3,K5]
	}
}
           

貪心算法注意事項和細節

1. 貪婪算法所得到的結果不一定是最優的結果(有時候會是最優解)，但是都是相對近似(接近)最優解的結果。
2. 比如上題的算法選出的是K1, K2, K3, K5，符合覆寫了全部的地區。
3. 但是我們發現 K2, K3,K4,K5 也可以覆寫全部地區，如果K2 的使用成本低于K1，那麼我們上題的 K1, K2, K3, K5 雖然是滿足條件，但是并不是最優的。

普裡姆算法

普裡姆算法介紹

1. 普利姆(Prim)算法求最小生成樹，也就是在包含n個頂點的連通圖中，找出隻有(n-1)條邊包含所有n個頂點的連通子圖，也就是所謂的極小連通子圖

2. 普利姆的算法如下:

   1）設G=(V,E)是連通網，T=(U,D)是最小生成樹，V,U是頂點集合，E,D是邊的集合

   2）若從頂點u開始構造最小生成樹，則從集合V中取出頂點u放入集合U中，标記頂點v的visited[u]=1

   3）若集合U中頂點ui與集合V-U中的頂點vj之間存在邊，則尋找這些邊中權值最小的邊，但不能構成回路，将頂點vj加入集合U中，将邊（ui,vj）加入集合D中，标記visited[vj]=1

   4）重複步驟②，直到U與V相等，即所有頂點都被标記為通路過，此時D中有n-1條邊

   5）提示: 單獨看步驟很難了解，我們通過代碼來講解，比較好了解

   

普裡姆算法最佳實踐(修路問題)

1. 有勝利鄉有7個村莊(A, B, C, D, E, F, G) ，現在需要修路把7個村莊連通
2. 各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公裡
3. 問：如何修路保證各個村莊都能連通，并且總的修建公路總裡程最短?

代碼實作

import java.util.Arrays;

public class PrimAlgorithm {

	public static void main(String[] args) {
		//測試看看圖是否建立ok
		char[] data = new char[]{'A','B','C','D','E','F','G'};
		int verxs = data.length;
		//鄰接矩陣的關系使用二維數組表示,10000這個大數，表示兩個點不聯通
		int [][]weight=new int[][]{
            {10000,5,7,10000,10000,10000,2},
            {5,10000,10000,9,10000,10000,3},
            {7,10000,10000,10000,8,10000,10000},
            {10000,9,10000,10000,10000,4,10000},
            {10000,10000,8,10000,10000,5,4},
            {10000,10000,10000,4,5,10000,6},
            {2,3,10000,10000,4,6,10000},};
            
        //建立MGraph對象
        MGraph graph = new MGraph(verxs);
        //建立一個MinTree對象
        MinTree minTree = new MinTree();
        minTree.createGraph(graph, verxs, data, weight);
        //輸出
        minTree.showGraph(graph);
        //測試普利姆算法
        minTree.prim(graph, 1);// 
	}

}

//建立最小生成樹->村莊的圖
class MinTree {
	//建立圖的鄰接矩陣
	/**
	 * 
	 * @param graph 圖對象
	 * @param verxs 圖對應的頂點個數
	 * @param data 圖的各個頂點的值
	 * @param weight 圖的鄰接矩陣
	 */
	public void createGraph(MGraph graph, int verxs, char data[], int[][] weight) {
		int i, j;
		for(i = 0; i < verxs; i++) {//頂點
			graph.data[i] = data[i];
			for(j = 0; j < verxs; j++) {
				graph.weight[i][j] = weight[i][j];
			}
		}
	}
	
	//顯示圖的鄰接矩陣
	public void showGraph(MGraph graph) {
		for(int[] link: graph.weight) {
			System.out.println(Arrays.toString(link));
		}
	}
	
	//編寫prim算法，得到最小生成樹
	/**
	 * 
	 * @param graph 圖
	 * @param v 表示從圖的第幾個頂點開始生成'A'->0 'B'->1...
	 */
	public void prim(MGraph graph, int v) {
		//visited[] 标記結點(頂點)是否被通路過
		int visited[] = new int[graph.verxs];
		//visited[] 預設元素的值都是0, 表示沒有通路過
//		for(int i =0; i <graph.verxs; i++) {
//			visited[i] = 0;
//		}
		
		//把目前這個結點标記為已通路
		visited[v] = 1;
		//h1 和 h2 記錄兩個頂點的下标
		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000; //将 minWeight 初始成一個大數，後面在周遊過程中，會被替換
		for(int k = 1; k < graph.verxs; k++) {//因為有 graph.verxs頂點，普利姆算法結束後，有 graph.verxs-1邊
			
			//這個是确定每一次生成的子圖 ，和哪個結點的距離最近
			for(int i = 0; i < graph.verxs; i++) {// i結點表示被通路過的結點
				for(int j = 0; j< graph.verxs;j++) {//j結點表示還沒有通路過的結點
					if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {
						//替換minWeight(尋找已經通路過的結點和未通路過的結點間的權值最小的邊)
						minWeight = graph.weight[i][j];
						h1 = i;
						h2 = j;
					}
				}
			}
			//找到一條邊是最小
			System.out.println("邊<" + graph.data[h1] + "," + graph.data[h2] + "> 權值:" + minWeight);
			//将目前這個結點标記為已經通路
			visited[h2] = 1;
			//minWeight 重新設定為最大值 10000
			minWeight = 10000;
		}
	}
}

class MGraph {
	int verxs; //表示圖的節點個數
	char[] data;//存放結點資料
	int[][] weight; //存放邊，就是我們的鄰接矩陣
	
	public MGraph(int verxs) {
		this.verxs = verxs;
		data = new char[verxs];
		weight = new int[verxs][verxs];
	}
}
           

克魯斯卡爾算法

克魯斯卡爾算法介紹

1. 克魯斯卡爾(Kruskal)算法，是用來求權重連通圖的最小生成樹的算法。
2. 基本思想：按照權值從小到大的順序選擇n-1條邊，并保證這n-1條邊不構成回路
3. 具體做法：首先構造一個隻含n個頂點的森林，然後依權值從小到大從連通網中選擇邊加入到森林中，并使森林中不産生回路，直至森林變成一棵樹為止

克魯斯卡爾算法圖解說明

以城市公交站問題來圖解說明 克魯斯卡爾算法的原理和步驟：

1. 在含有n個頂點的連通圖中選擇n-1條邊，構成一棵極小連通子圖，并使該連通子圖中n-1條邊上權值之和達到最小，則稱其為連通網的最小生成樹。

   

   

代碼實作

import java.util.Arrays;

public class KruskalCase {

	private int edgeNum; //邊的個數
	private char[] vertexs; //頂點數組
	private int[][] matrix; //鄰接矩陣
	//使用 INF 表示兩個頂點不能連通
	private static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) {
		char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
		//克魯斯卡爾算法的鄰接矩陣  
	      int matrix[][] = {
	      /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
	/*A*/ {   0,  12, INF, INF, INF,  16,  14},
	/*B*/ {  12,   0,  10, INF, INF,   7, INF},
	/*C*/ { INF,  10,   0,   3,   5,   6, INF},
	/*D*/ { INF, INF,   3,   0,   4, INF, INF},
	/*E*/ { INF, INF,   5,   4,   0,   2,   8},
	/*F*/ {  16,   7,   6, INF,   2,   0,   9},
	/*G*/ {  14, INF, INF, INF,   8,   9,   0}}; 
	      //大家可以在去測試其它的鄰接矩陣，結果都可以得到最小生成樹.
	      
	      //建立KruskalCase 對象執行個體
	      KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
	      //輸出建構的
	      kruskalCase.print();
	      kruskalCase.kruskal();
	      
	}
	
	//構造器
	public KruskalCase(char[] vertexs, int[][] matrix) {
		//初始化頂點數和邊的個數
		int vlen = vertexs.length;
		
		//初始化頂點, 複制拷貝的方式
		this.vertexs = new char[vlen];
		for(int i = 0; i < vertexs.length; i++) {
			this.vertexs[i] = vertexs[i];
		}
		
		//初始化邊, 使用的是複制拷貝的方式
		this.matrix = new int[vlen][vlen];
		for(int i = 0; i < vlen; i++) {
			for(int j= 0; j < vlen; j++) {
				this.matrix[i][j] = matrix[i][j];
			}
		}
		//統計邊的條數
		for(int i =0; i < vlen; i++) {
			for(int j = i+1; j < vlen; j++) {
				if(this.matrix[i][j] != INF) {
					edgeNum++;
				}
			}
		}
		
	}
	public void kruskal() {
		int index = 0; //表示最後結果數組的索引
		int[] ends = new int[edgeNum]; //用于儲存"已有最小生成樹" 中的每個頂點在最小生成樹中的終點
		//建立結果數組, 儲存最後的最小生成樹
		EData[] rets = new EData[edgeNum];
		
		//擷取圖中 所有的邊的集合 ， 一共有12邊
		EData[] edges = getEdges();
		System.out.println("圖的邊的集合=" + Arrays.toString(edges) + " 共"+ edges.length); //12
		
		//按照邊的權值大小進行排序(從小到大)
		sortEdges(edges);
		
		//周遊edges 數組，将邊添加到最小生成樹中時，判斷是準備加入的邊否形成了回路，如果沒有，就加入 rets, 否則不能加入
		for(int i=0; i < edgeNum; i++) {
			//擷取到第i條邊的第一個頂點(起點)
			int p1 = getPosition(edges[i].start); //p1=4
			//擷取到第i條邊的第2個頂點
			int p2 = getPosition(edges[i].end); //p2 = 5
			
			//擷取p1這個頂點在已有最小生成樹中的終點
			int m = getEnd(ends, p1); //m = 4
			//擷取p2這個頂點在已有最小生成樹中的終點
			int n = getEnd(ends, p2); // n = 5
			//是否構成回路
			if(m != n) { //沒有構成回路
				ends[m] = n; // 設定m 在"已有最小生成樹"中的終點 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
				rets[index++] = edges[i]; //有一條邊加入到rets數組
			}
		}
		//<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
		//統計并列印 "最小生成樹", 輸出  rets
		System.out.println("最小生成樹為");
		for(int i = 0; i < index; i++) {
			System.out.println(rets[i]);
		}
		
		
	}
	
	//列印鄰接矩陣
	public void print() {
		System.out.println("鄰接矩陣為: \n");
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=0; j < vertexs.length; j++) {
				System.out.printf("%12d", matrix[i][j]);
			}
			System.out.println();//換行
		}
	}

	/**
	 * 功能：對邊進行排序處理, 冒泡排序
	 * @param edges 邊的集合
	 */
	private void sortEdges(EData[] edges) {
		for(int i = 0; i < edges.length - 1; i++) {
			for(int j = 0; j < edges.length - 1 - i; j++) {
				if(edges[j].weight > edges[j+1].weight) {//交換
					EData tmp = edges[j];
					edges[j] = edges[j+1];
					edges[j+1] = tmp;
				}
			}
 		}
	}
	/**
	 * 
	 * @param ch 頂點的值，比如'A','B'
	 * @return 傳回ch頂點對應的下标，如果找不到，傳回-1
	 */
	private int getPosition(char ch) {
		for(int i = 0; i < vertexs.length; i++) {
			if(vertexs[i] == ch) {//找到
				return i;
			}
		}
		//找不到,傳回-1
		return -1;
	}
	/**
	 * 功能: 擷取圖中邊，放到EData[] 數組中，後面我們需要周遊該數組
	 * 是通過matrix 鄰接矩陣來擷取
	 * EData[] 形式 [['A','B', 12], ['B','F',7], .....]
	 * @return
	 */
	private EData[] getEdges() {
		int index = 0;
		EData[] edges = new EData[edgeNum];
		for(int i = 0; i < vertexs.length; i++) {
			for(int j=i+1; j <vertexs.length; j++) {
				if(matrix[i][j] != INF) {
					edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
				}
			}
		}
		return edges;
	}
	/**
	 * 功能: 擷取下标為i的頂點的終點(), 用于後面判斷兩個頂點的終點是否相同
	 * @param ends ： 數組就是記錄了各個頂點對應的終點是哪個,ends 數組是在周遊過程中，逐漸形成
	 * @param i : 表示傳入的頂點對應的下标
	 * @return 傳回的就是 下标為i的這個頂點對應的終點的下标, 一會回頭還有來了解
	 */
	private int getEnd(int[] ends, int i) { // i = 4 [0,0,0,0,5,0,0,0,0,0,0,0]
		while(ends[i] != 0) {
			i = ends[i];
		}
		return i;
	}
 
}

//建立一個類EData ，它的對象執行個體就表示一條邊
class EData {
	char start; //邊的一個點
	char end; //邊的另外一個點
	int weight; //邊的權值
	//構造器
	public EData(char start, char end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
	//重寫toString, 便于輸出邊資訊
	@Override
	public String toString() {
		return "EData [<" + start + ", " + end + ">= " + weight + "]";
	}
}
           

迪傑斯特拉算法

迪傑斯特拉(Dijkstra)算法介紹

迪傑斯特拉(Dijkstra)算法是典型最短路徑算法，用于計算一個結點到其他結點的最短路徑。 它的主要特點是以起始點為中心向外層層擴充(廣度優先搜尋思想)，直到擴充到終點為止。

迪傑斯特拉(Dijkstra)算法過程

設定出發頂點為v，頂點集合V{v1,v2,vi…}，v到V中各頂點的距離構成距離集合Dis，Dis{d1,d2,di…}，Dis集合記錄着v到圖中各頂點的距離(到自身可以看作0，v到vi距離對應為di)

1. 從Dis中選擇值最小的di并移出Dis集合，同時移出V集合中對應的頂點vi，此時的v到vi即為最短路徑
2. 更新Dis集合，更新規則為：比較v到V集合中頂點的距離值，與v通過vi到V集合中頂點的距離值，保留值較小的一個(同時也應該更新頂點的前驅節點為vi，表明是通過vi到達的)
3. 重複執行兩步驟，直到最短路徑頂點為目标頂點即可結束

迪傑斯特拉(Dijkstra)算法最佳應用-最短路徑

1. 戰争時期，勝利鄉有7個村莊(A, B, C, D, E, F, G) ，現在有六個郵差，從G點出發，需要分别把郵件分别送到 A, B, C , D, E, F 六個村莊
2. 各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公裡
3. 問：如何計算出G村莊到 其它各個村莊的最短距離?
4. 如果從其它點出發到各個點的最短距離又是多少?

代碼實作

import java.util.Arrays;

public class DijkstraAlgorithm {

	public static void main(String[] args) {
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		//鄰接矩陣
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;// 表示不可以連接配接
		matrix[0]=new int[]{N,5,7,N,N,N,2};  
        matrix[1]=new int[]{5,N,N,9,N,N,3};  
        matrix[2]=new int[]{7,N,N,N,8,N,N};  
        matrix[3]=new int[]{N,9,N,N,N,4,N};  
        matrix[4]=new int[]{N,N,8,N,N,5,4};  
        matrix[5]=new int[]{N,N,N,4,5,N,6};  
        matrix[6]=new int[]{2,3,N,N,4,6,N};
        //建立 Graph對象
        Graph graph = new Graph(vertex, matrix);
        //測試, 看看圖的鄰接矩陣是否ok
        graph.showGraph();
        //測試迪傑斯特拉算法
        graph.dsj(2);//C
        graph.showDijkstra();
        
        
	}

}

class Graph {
	private char[] vertex; // 頂點數組
	private int[][] matrix; // 鄰接矩陣
	private VisitedVertex vv; //已經通路的頂點的集合

	// 構造器
	public Graph(char[] vertex, int[][] matrix) {
		this.vertex = vertex;
		this.matrix = matrix;
	}
	
	//顯示結果
	public void showDijkstra() {
		vv.show();
	}

	// 顯示圖
	public void showGraph() {
		for (int[] link : matrix) {
			System.out.println(Arrays.toString(link));
		}
	}
	
	//迪傑斯特拉算法實作
	/**
	 * 
	 * @param index 表示出發頂點對應的下标
	 */
	public void dsj(int index) {
		vv = new VisitedVertex(vertex.length, index);
		update(index);//更新index頂點到周圍頂點的距離和前驅頂點
		for(int j = 1; j <vertex.length; j++) {
			index = vv.updateArr();// 選擇并傳回新的通路頂點
			update(index); // 更新index頂點到周圍頂點的距離和前驅頂點
		} 
	}
	
	
	
	//更新index下标頂點到周圍頂點的距離和周圍頂點的前驅頂點,
	private void update(int index) {
		int len = 0;
		//根據周遊我們的鄰接矩陣的  matrix[index]行
		for(int j = 0; j < matrix[index].length; j++) {
			// len 含義是 : 出發頂點到index頂點的距離 + 從index頂點到j頂點的距離的和 
			len = vv.getDis(index) + matrix[index][j];
			// 如果j頂點沒有被通路過，并且 len 小于出發頂點到j頂點的距離，就需要更新
			if(!vv.in(j) && len < vv.getDis(j)) {
				vv.updatePre(j, index); //更新j頂點的前驅為index頂點
				vv.updateDis(j, len); //更新出發頂點到j頂點的距離
			}
		}
	}
}

// 已通路頂點集合
class VisitedVertex {
	// 記錄各個頂點是否通路過 1表示通路過,0未通路,會動态更新
	public int[] already_arr;
	// 每個下标對應的值為前一個頂點下标, 會動态更新
	public int[] pre_visited;
	// 記錄出發頂點到其他所有頂點的距離,比如G為出發頂點，就會記錄G到其它頂點的距離，會動态更新，求的最短距離就會存放到dis
	public int[] dis;
	
	//構造器
	/**
	 * 
	 * @param length :表示頂點的個數 
	 * @param index: 出發頂點對應的下标, 比如G頂點，下标就是6
	 */
	public VisitedVertex(int length, int index) {
		this.already_arr = new int[length];
		this.pre_visited = new int[length];
		this.dis = new int[length];
		//初始化 dis數組
		Arrays.fill(dis, 65535);
		this.already_arr[index] = 1; //設定出發頂點被通路過
		this.dis[index] = 0;//設定出發頂點的通路距離為0
				
	}
	/**
	 * 功能: 判斷index頂點是否被通路過
	 * @param index
	 * @return 如果通路過，就傳回true, 否則通路false
	 */
	public boolean in(int index) {
		return already_arr[index] == 1;
	}
	
	/**
	 * 功能: 更新出發頂點到index頂點的距離
	 * @param index
	 * @param len
	 */
	public void updateDis(int index, int len) {
		dis[index] = len;
	}
	/**
	 * 功能: 更新pre這個頂點的前驅頂點為index頂點
	 * @param pre
	 * @param index
	 */
	public void updatePre(int pre, int index) {
		pre_visited[pre] = index;
	}
	/**
	 * 功能:傳回出發頂點到index頂點的距離
	 * @param index
	 */
	public int getDis(int index) {
		return dis[index];
	}
	
	/**
	 * 繼續選擇并傳回新的通路頂點， 比如這裡的G 完後，就是 A點作為新的通路頂點(注意不是出發頂點)
	 * @return
	 */
	public int updateArr() {
		int min = 65535, index = 0;
		for(int i = 0; i < already_arr.length; i++) {
			if(already_arr[i] == 0 && dis[i] < min ) {
				min = dis[i];
				index = i;
			}
		}
		//更新 index 頂點被通路過
		already_arr[index] = 1;
		return index;
	}
	
	//顯示最後的結果
	//即将三個數組的情況輸出
	public void show() {
		
		System.out.println("==========================");
		//輸出already_arr
		for(int i : already_arr) {
			System.out.print(i + " ");
		}
		System.out.println();
		//輸出pre_visited
		for(int i : pre_visited) {
			System.out.print(i + " ");
		}
		System.out.println();
		//輸出dis
		for(int i : dis) {
			System.out.print(i + " ");
		}
		System.out.println();
		//為了好看最後的最短距離，我們處理
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		int count = 0;
		for (int i : dis) {
			if (i != 65535) {
				System.out.print(vertex[count] + "("+i+") ");
			} else {
				System.out.println("N ");
			}
			count++;
		}
		System.out.println();
	}
}
           

弗洛伊德算法

弗洛伊德(Floyd)算法介紹

1. 和Dijkstra算法一樣，弗洛伊德(Floyd)算法也是一種用于尋找給定的權重圖中頂點間最短路徑的算法。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。
2. 弗洛伊德算法(Floyd)計算圖中各個頂點之間的最短路徑。
3. 迪傑斯特拉算法用于計算圖中某一個頂點到其他頂點的最短路徑。
4. 弗洛伊德算法 VS 迪傑斯特拉算法：迪傑斯特拉算法通過標明的被通路頂點，求出從出發通路頂點到其他頂點的最短路徑；弗洛伊德算法中每一個頂點都是出發通路點，是以需要将每一個頂點看做被通路頂點，求出從每一個頂點到其他頂點的最短路徑。

弗洛伊德(Floyd)算法圖解分析

1. 設定頂點vi到頂點vk的最短路徑已知為Lik，頂點vk到vj的最短路徑已知為Lkj，頂點vi到vj的路徑為Lij，則vi到vj的最短路徑為：min((Lik+Lkj),Lij)，vk的取值為圖中所有頂點，則可獲得vi到vj的最短路徑。
2. 至于vi到vk的最短路徑Lik或者vk到vj的最短路徑Lkj，是以同樣的方式獲得。

弗洛伊德(Floyd)算法最佳應用-最短路徑

1）勝利鄉有7個村莊(A, B, C, D, E, F, G)

2）各個村莊的距離用邊線表示(權) ，比如 A – B 距離 5公裡

3）問：如何計算出各村莊到 其它各村莊的最短距離?

代碼實作

import java.util.Arrays;

public class FloydAlgorithm {

	public static void main(String[] args) {
		// 測試看看圖是否建立成功
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		//建立鄰接矩陣
		int[][] matrix = new int[vertex.length][vertex.length];
		final int N = 65535;
		matrix[0] = new int[] { 0, 5, 7, N, N, N, 2 };
		matrix[1] = new int[] { 5, 0, N, 9, N, N, 3 };
		matrix[2] = new int[] { 7, N, 0, N, 8, N, N };
		matrix[3] = new int[] { N, 9, N, 0, N, 4, N };
		matrix[4] = new int[] { N, N, 8, N, 0, 5, 4 };
		matrix[5] = new int[] { N, N, N, 4, 5, 0, 6 };
		matrix[6] = new int[] { 2, 3, N, N, 4, 6, 0 };
		
		//建立 Graph 對象
		Graph graph = new Graph(vertex.length, matrix, vertex);
		//調用弗洛伊德算法
		graph.floyd();
		graph.show();
	}

}

// 建立圖
class Graph {
	private char[] vertex; // 存放頂點的數組
	private int[][] dis; // 儲存，從各個頂點出發到其它頂點的距離，最後的結果，也是保留在該數組
	private int[][] pre;// 儲存到達目标頂點的前驅頂點

	// 構造器
	/**
	 * 
	 * @param length
	 *            大小
	 * @param matrix
	 *            鄰接矩陣
	 * @param vertex
	 *            頂點數組
	 */
	public Graph(int length, int[][] matrix, char[] vertex) {
		this.vertex = vertex;
		this.dis = matrix;
		this.pre = new int[length][length];
		// 對pre數組初始化, 注意存放的是前驅頂點的下标
		for (int i = 0; i < length; i++) {
			Arrays.fill(pre[i], i);
		}
	}

	// 顯示pre數組和dis數組
	public void show() {

		//為了顯示便于閱讀，我們優化一下輸出
		char[] vertex = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
		for (int k = 0; k < dis.length; k++) {
			// 先将pre數組輸出的一行
			for (int i = 0; i < dis.length; i++) {
				System.out.print(vertex[pre[k][i]] + " ");
			}
			System.out.println();
			// 輸出dis數組的一行資料
			for (int i = 0; i < dis.length; i++) {
				System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路徑是" + dis[k][i] + ") ");
			}
			System.out.println();
			System.out.println();

		}

	}
	
	//弗洛伊德算法, 比較容易了解，而且容易實作
	public void floyd() {
		int len = 0; //變量儲存距離
		//對中間頂點周遊， k 就是中間頂點的下标 [A, B, C, D, E, F, G] 
		for(int k = 0; k < dis.length; k++) { // 
			//從i頂點開始出發 [A, B, C, D, E, F, G]
			for(int i = 0; i < dis.length; i++) {
				//到達j頂點 // [A, B, C, D, E, F, G]
				for(int j = 0; j < dis.length; j++) {
					len = dis[i][k] + dis[k][j];// => 求出從i 頂點出發，經過 k中間頂點，到達 j 頂點距離
					if(len < dis[i][j]) {//如果len小于 dis[i][j]
						dis[i][j] = len;//更新距離
						pre[i][j] = pre[k][j];//更新前驅頂點
					}
				}
			}
		}
	}
}
           

馬踏棋盤算法

馬踏棋盤算法介紹和遊戲示範

1. 馬踏棋盤算法也被稱為騎士周遊問題
2. 将馬随機放在國際象棋的8×8棋盤Board[0～7][0～7]的某個方格中，馬按走棋規則(馬走日字)進行移動。要求每個方格隻進入一次，走遍棋盤上全部64個方格
3. 遊戲示範: http://www.4399.com/flash/146267_2.htm

   

馬踏棋盤遊戲代碼實作

1. 馬踏棋盤問題(騎士周遊問題)實際上是圖的深度優先搜尋(DFS)的應用。

2. 如果使用回溯（就是深度優先搜尋）來解決，假如馬兒踏了53個點，如圖：走到了第53個，坐标（1,0），發現已經走到盡頭，沒辦法，那就隻能回退了，檢視其他的路徑，就在棋盤上不停的回溯…… ，思路分析+代碼實作

   對第一種方式的思路圖解

   

3. 分析第一種方式的問題，并使用貪心算法（greedyalgorithm）進行優化。解決馬踏棋盤問題.

   

4. 使用前面的遊戲來驗證算法是否正确。

代碼實作

import java.awt.Point;
import java.util.ArrayList;
import java.util.Comparator;

public class HorseChessboard {

	private static int X; // 棋盤的列數
	private static int Y; // 棋盤的行數
	//建立一個數組，标記棋盤的各個位置是否被通路過
	private static boolean visited[];
	//使用一個屬性，标記是否棋盤的所有位置都被通路
	private static boolean finished; // 如果為true,表示成功
	
	public static void main(String[] args) {
		System.out.println("騎士周遊算法，開始運作~~");
		//測試騎士周遊算法是否正确
		X = 8;
		Y = 8;
		int row = 1; //馬兒初始位置的行，從1開始編号
		int column = 1; //馬兒初始位置的列，從1開始編号
		//建立棋盤
		int[][] chessboard = new int[X][Y];
		visited = new boolean[X * Y];//初始值都是false
		//測試一下耗時
		long start = System.currentTimeMillis();
		traversalChessboard(chessboard, row - 1, column - 1, 1);
		long end = System.currentTimeMillis();
		System.out.println("共耗時: " + (end - start) + " 毫秒");
		
		//輸出棋盤的最後情況
		for(int[] rows : chessboard) {
			for(int step: rows) {
				System.out.print(step + "\t");
			}
			System.out.println();
		}
	}
	
	/**
	 * 完成騎士周遊問題的算法
	 * @param chessboard 棋盤
	 * @param row 馬兒目前的位置的行 從0開始 
	 * @param column 馬兒目前的位置的列  從0開始
	 * @param step 是第幾步 ,初始位置就是第1步 
	 */
	public static void traversalChessboard(int[][] chessboard, int row, int column, int step) {
		chessboard[row][column] = step;
		//row = 4 X = 8 column = 4 = 4 * 8 + 4 = 36
		visited[row * X + column] = true; //标記該位置已經通路
		//擷取目前位置可以走的下一個位置的集合 
		ArrayList<Point> ps = next(new Point(column, row));
		//對ps進行排序,排序的規則就是對ps的所有的Point對象的下一步的位置的數目，進行非遞減排序
		sort(ps);
		//周遊 ps
		while(!ps.isEmpty()) {
			Point p = ps.remove(0);//取出下一個可以走的位置
			//判斷該點是否已經通路過
			if(!visited[p.y * X + p.x]) {//說明還沒有通路過
				traversalChessboard(chessboard, p.y, p.x, step + 1);
			}
		}
		//判斷馬兒是否完成了任務，使用   step 和應該走的步數比較 ， 
		//如果沒有達到數量，則表示沒有完成任務，将整個棋盤置0
		//說明: step < X * Y  成立的情況有兩種
		//1. 棋盤到目前位置,仍然沒有走完
		//2. 棋盤處于一個回溯過程
		if(step < X * Y && !finished ) {
			chessboard[row][column] = 0;
			visited[row * X + column] = false;
		} else {
			finished = true;
		}
		
	}
	
	/**
	 * 功能： 根據目前位置(Point對象)，計算馬兒還能走哪些位置(Point)，并放入到一個集合中(ArrayList), 最多有8個位置
	 * @param curPoint
	 * @return
	 */
	public static ArrayList<Point> next(Point curPoint) {
		//建立一個ArrayList
		ArrayList<Point> ps = new ArrayList<Point>();
		//建立一個Point
		Point p1 = new Point();
		//表示馬兒可以走5這個位置
		if((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y -1) >= 0) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走6這個位置
		if((p1.x = curPoint.x - 1) >=0 && (p1.y=curPoint.y-2)>=0) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走7這個位置
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走0這個位置
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走1這個位置
		if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走2這個位置
		if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走3這個位置
		if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
			ps.add(new Point(p1));
		}
		//判斷馬兒可以走4這個位置
		if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
			ps.add(new Point(p1));
		}
		return ps;
	}

	//根據目前這個一步的所有的下一步的選擇位置，進行非遞減排序, 減少回溯的次數
	public static void sort(ArrayList<Point> ps) {
		ps.sort(new Comparator<Point>() {
			@Override
			public int compare(Point o1, Point o2) {
				// TODO Auto-generated method stub
				//擷取到o1的下一步的所有位置個數
				int count1 = next(o1).size();
				//擷取到o2的下一步的所有位置個數
				int count2 = next(o2).size();
				if(count1 < count2) {
					return -1;
				} else if (count1 == count2) {
					return 0;
				} else {
					return 1;
				}
			}	
		});
	}
}
           

學習連接配接：

https://www.bilibili.com/video/BV1E4411H73v