??? --sunfruit
上圖求一筆畫的路徑，利用圖論的相關(guān)知識可以得到程序如下：
public class OnePath {
??? private static int[][]
??????????? links = { {0,1,1,0,0,0,1,0}, {1,0,0,1,0,0,0,1}, {1,0,0,1,1,1,0,0},
??????????? {0,1,1,0,1,1,0,0}, {0,0,1,1,0,1,1,0}, {0,0,1,1,1,0,0,1}, {1,0,0,0,1,0,0,0}, {0,1,0,0,0,1,0,0}
??? };
??? public OnePath() {
??????? int sum = 0;
??????? //存放每個點的度
??????? int[] point = new int[links[0].length];
??????? for (int i = 0; i < links[0].length; i++) {
??????????? int[] templink = links[i];
??????????? for (int j = 0; j < links[0].length; j++) {
??????????????? point[i] += templink[j];
??????????? }
??????????? sum += point[i];
??????? }
??????? //計算度數(shù)是奇數(shù)點的個數(shù),如果大于2則不能一筆畫
??????? int odt = 0;
??????? int start = -1;
??????? for (int i = 0; i < point.length; i++) {
??????????? int mod = point[i] % 2;
??????????? if (mod > 0) {
??????????????? //if(start==-1)
??????????????????? start = i;
??????????????? odt++;
??????????? }
??????? }
??????? if(odt>2)
??????? {
????????? System.out.println("該圖不能一筆畫");
????????? return;
??????? }
??????? int r = 0;
??????? //從一個奇數(shù)點開始計算
??????? int nowd=start;
??????? System.out.print(nowd+1);
??????? while (sum > 0) {
??????????? r=0;
??????????? //對于起點nowd 檢查當(dāng)前的點r 是否合適
??????????? //links[nowd][r]==0 判斷是否有可以走的沒有用過的線路
??????????? //(point[r]<=1 && sum!=2) 判斷是否是最后一次，如果不是最后一次，那么避開度數(shù)是1的點
??????????? while (links[nowd][r]==0 || (point[r]<=1 && sum!=2)) {
??????????????? r++;
??????????? }
??????????? links[nowd][r]=0; //已經(jīng)用過的線路
??????????? links[r][nowd]=0; //已經(jīng)用過的線路 links[nowd][r] links[r][nowd]互為往返路線,用過1->2那么2->1也作廢了
??????????? sum=sum-2; //總度數(shù)減2 因為從1->2 消耗了1的度和2的度
??????????? point[nowd]--; //起點和終點的度都減1 1->2 那么1的度和2的度都減1
??????????? point[r]--; //起點和終點的度都減1 1->2 那么1的度和2的度都減1
??????????? nowd =r; //設(shè)置新的起點
??????????? System.out.print("->"+(r+1));
??????? }
??? }
??? public static void main(String[] args) {
??????? new OnePath();
??? }
}