sunfruit[请访问http://www.fruitres.cn]

--我相信JAVA能走得更远 QQ:316228067

[原创]图论应用--一笔画问题

    --sunfruit
tu1_2.gif
上图求一笔画的路径,利用图论的相关知识可以得到程序如下:

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();
    }

}

posted on 2006-08-31 14:20 sunfruit 阅读(929) 评论(0)  编辑  收藏 所属分类: 数据结构


只有注册用户登录后才能发表评论。


网站导航: