--sunfruit
上图求一笔画的路径，利用图论的相关知识可以得到程序如下：
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];
}
//计算度数是奇数点的个数,如果大于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;
//从一个奇数点开始计算
int nowd=start;
System.out.print(nowd+1);
while (sum > 0) {
r=0;
//对于起点nowd 检查当前的点r 是否合适
//links[nowd][r]==0 判断是否有可以走的没有用过的线路
//(point[r]<=1 && sum!=2) 判断是否是最后一次，如果不是最后一次，那么避开度数是1的点
while (links[nowd][r]==0 || (point[r]<=1 && sum!=2)) {
r++;
}
links[nowd][r]=0; //已经用过的线路
links[r][nowd]=0; //已经用过的线路 links[nowd][r] links[r][nowd]互为往返路线,用过1->2那么2->1也作废了
sum=sum-2; //总度数减2 因为从1->2 消耗了1的度和2的度
point[nowd]--; //起点和终点的度都减1 1->2 那么1的度和2的度都减1
point[r]--; //起点和终点的度都减1 1->2 那么1的度和2的度都减1
nowd =r; //设置新的起点
System.out.print("->"+(r+1));
}
}
public static void main(String[] args) {
new OnePath();
}
}