1 问题描述
汉密尔顿电路是什么？
引自百度百科：
汉密尔顿图(汉密尔顿图) (英语： Hamiltonian path，或Traceable path ) )是天文学家汉密尔顿提出的无向图，从指定的起点到指定的终点，中途通过所有其他节点在图论中是指包含哈密顿回路的图，将封闭的哈密顿路径称为哈密顿回路(Hamiltonian cycle )，将包含图的所有顶点的路径称为哈密顿路径。
这里需要解决的问题：给定一个图，判断该图是否包含哈密顿回路？ 如果包括，则输出其中一个哈密顿回路，如果不包括，则不输出任何内容。
2 解决方案
为了寻找汉密尔顿电路，我们使用了递归和回溯这一深度优先搜索方法。
以下代码中使用的图数据如下：
package com.liuzhen.chapter12； 公共类Hamilton circuit {/* *参数adjMatrix :指定图表的邻接矩阵。 其中，值为1表示两个顶点是公共的，-1表示两个顶点不是公共的。 */publicvoidgethamiltoncircuit (int (() ) ) )//图中的顶点是否已访问int [ ] path=new int [ adj matrix.length ] //记录哈密顿回路路径for (inti=0； i adjMatrix.length； I ) { used[i]=false； //初始化，所有顶点均为path[i]=-1； //初始化、未选择起点以及到达了哪个顶点} used[0]=true；//表示从第一个顶点开始遍历path[0]=0； //表示哈密顿回路的起点是第0个顶点DFS (adj matrix，path，used，1 )； 从第//0个顶点开始进行深度优先的遍历，如果有汉密尔顿电路，就输出1个循环。 否则，无输出(/**参数step:当前走的步骤数，即已经遍历的顶点数(/publicbooleanDFS(int () adjmatrix，int ) ) pat attats int step (if (step==adj matrix.length ) /图中的所有顶点if ) adjmatrix[path[step-1](0)==1) /返回在最后一个步骤中到达的顶点I ) system.out.print (() ) (char ) ) path[i] 'a ' ) ) —— )； system.out.print (() ) (char ) ) path[0] 'a ' ) ) System.out.println (； 返回真； } return false； (else ) for ) intI=0； i adjMatrix.length； I ) if (！ used [ I ] adj matrix [ 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； } publicstaticvoidmain (string [ ] args ) hamiltoncircuittest=newhamiltoncircuit )； int [ ] [ ] adj matrix={-1，1，1，-1，-1，-1，-1，}、{ 1，1，-1，-1}、1，-1，-1 }} 运行结果：
a —— b —— f —— e —— c —— d —— a