难题讲述 2 style="font-family: 金鼎文;">化解方案   亚洲必赢官网app,1 难题讲述 何以是乌兰察布顿回路? 引用自百度百科: 日喀则顿图(中卫尔顿图)(阿拉伯语:汉密尔顿ian path,或Traceable path)是二个无向图,由天思想家金昌顿指出,由指定的起源前往指定的终端,途..." />

景德镇顿回路难题

By admin in 亚洲必赢官网app on 2019年2月16日

目录

1 style=”font-family: 石籀文;”>难题讲述

2 style=”font-family: 金鼎文;”>化解方案

 


亚洲必赢官网app,1 难题讲述

何以是乌兰察布顿回路?

引用自百度百科:

日喀则顿图(中卫尔顿图)(阿拉伯语:汉密尔顿ian
path,或Traceable path)是二个无向图,由天思想家金昌顿指出,由指定的起源前往指定的终端,途中经过全体其余节点且只经过五回在图论中是指包罗随州顿回路的图,闭合的武威顿路径称作新余顿回路(**Hamiltonian cycle),含有图中全数终端的不二法门称作中卫顿路径。**

今昔本文要化解的题材:给定多少个图,判断那几个图是不是带有乌兰察布顿回路?假使含有,输出其中一条达州顿回路,尽管不含有,则无其余输出。

 


2 化解方案

正文寻找金昌顿回路,运用了深度优先搜索方法,即递归和追忆法思想。

下边代码所用图数据如下:

亚洲必赢官网app 1

 

具体代码如下:

package com.liuzhen.chapter12;

public class HamiltonCircuit {
    /*
     * 参数adjMatrix:给定图的邻接矩阵,其中值为1表示两个顶点可以相通,值为-1表示两个顶点不能相通
     */
    public void getHamiltonCircuit(int[][] adjMatrix) {
        boolean[] used = new boolean[adjMatrix.length];       //用于标记图中顶点是否被访问
        int[] path = new int[adjMatrix.length];       //记录哈密顿回路路径
        for(int i = 0;i < adjMatrix.length;i++) {
            used[i] = false;     //初始化,所有顶点均未被遍历
            path[i] = -1;        //初始化,未选中起点及到达任何顶点
        }
        used[0] = true;          //表示从第1个顶点开始遍历
        path[0] = 0;             //表示哈密顿回路起点为第0个顶点
        dfs(adjMatrix, path, used, 1);     //从第0个顶点开始进行深度优先遍历,如果存在哈密顿回路,输出一条回路,否则无输出
    }
    /*
     * 参数step:当前行走的步数,即已经遍历顶点的个数
     */
    public boolean dfs(int[][] adjMatrix, int[] path, boolean[] used, int step) {
        if(step == adjMatrix.length) {     //当已经遍历完图中所有顶点
            if(adjMatrix[path[step - 1]][0] == 1) { //最后一步到达的顶点能够回到起点
                for(int i = 0;i < path.length;i++)
                    System.out.print(((char)(path[i] + 'a'))+"——>");
                System.out.print(((char)(path[0] + 'a')));
                System.out.println();
                return true;
            }
            return false;
        } else {
            for(int i = 0;i < adjMatrix.length;i++) {
                if(!used[i] && adjMatrix[path[step - 1]][i] == 1) {
                    used[i] = true;
                    path[step] = i;
                    if(dfs(adjMatrix, path, used, step + 1))
                        return true;
                    else {
                        used[i] = false;    //进行回溯处理
                        path[step] = -1;
                    }
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        HamiltonCircuit test = new HamiltonCircuit();
        int[][] adjMatrix = {{-1,1,1,1,-1,-1},
                {1,-1,1,-1,-1,1},
                {1,1,-1,1,1,-1},
                {1,-1,1,-1,1,-1},
                {-1,-1,1,1,-1,1},
                {-1,1,-1,-1,1,-1}};
        test.getHamiltonCircuit(adjMatrix);
    }
}

运营结果:

a——>b——>f——>e——>c——>d——>a

 

 

 

参考资料:

1.基于回溯法寻找雅安顿回路

2.《算法设计与分析基础》第2版
  Anany Levitin 著  潘彦 译

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 亚洲必赢手机官网 版权所有