离散数学实验（图论部分汉密尔顿图回路问题）

背景知识

考虑汉密尔顿的判定和求汉密尔顿回路的问题
汉密尔顿问题对应于在一个连通图上求通过所有结点一次且仅一次的回路问题，这个问题是一个NPC难题，因此一直没有特别有效的算法。
判断一个连通图是不是汉密尔顿图最基本的方法就是使用递归穷举的方法。递归穷举的方式对于结点数较少的连通图是比较有效的，但是这种方法毕竟有限，而且速度较慢。
对于汉密尔顿图的判定问题，可以首先采用一些非常简便的判定方法来确定一个连通路是不是汉密尔顿图，例如：汉密尔顿图的判定并没有充分必要条件，只有几个充分条件和几个必要条件可以使用，我们可以首先利用一些计算非常方便的充分条件来判定一个连通图是汉密尔顿图，比如利用下面提到的一些定理：
①若连通图各节点度数满足d（v_1 ）<d(v_2)<⋯<d(v_n)，并且对任一m<n/2，满足d(v_m)<m和d(v_(n-m))<n-m，此图一定是汉密尔顿图。
②若一连通图的闭包是完全图，则此连通图一定是汉密尔顿图。
尝试将这些定理加入到汉密尔顿图的判定当中，之后这些定理无法判定的时候，才需要采用递归的方式来解决。

实验内容

①实现深度优先搜索方式的递归汉密尔顿图的判定和汉密尔顿回路求解，
②计算时间复杂度，给出节点数为5,10,20,100情况下的运行时间，并模拟出算法效率曲线图，
③实现使用部分计算简便的充分条件来实现汉密尔顿图判定的算法。
根据以上提示的完整代码：

import java.util.Scanner;

class gethamiltion {

	static int visit[] = new int[100]; // 节点访问记录
	static int loop[] = new int[100];// 汉密尔顿回路记录
	static Boolean check = false;
	static int cnt = 0;

	Boolean quickcheck(int matrixs[][], int v) // 此方法判断是否是完全图，如果是完全图，则不用递归直接结束，是判断汉密尔顿图的简便充分条件。
	{
		Boolean check = true;
		for (int i = 1; i <= v; i++) {
			for (int j = 1; j <= v; j++) {
				if (matrixs[i][j] != 1) {
					check = false;
					return check;
				}
			}
		}
		return check;
	}

	Boolean dfshamiltion(int matrixs[][], int start, int length, int v) // dfs深度优先搜索判断是否是汉密尔顿图，loop[]存汉密尔顿路
	{
		int i;
		if (length == v && matrixs[start][1] == 1) {
			loop[length + 1] = start;
			check = true;
			// System.out.println("start:"+start);
			// System.out.println("length:"+length);
			// System.out.println("cnt："+cnt);
		}
		for (i = 1; i <= v; i++) {
			if (matrixs[start][i] == 1 && visit[i] == 0 && start != i) {
				visit[start] = 1;
				length++;
				loop[length] = start;
				dfshamiltion(matrixs, i, length, v);
				break;
			} else if (start != 1 && matrixs[start][i] == 0 && visit[i] == 0) {
				// length ++;
				cnt++;
			}
		}
		return check;
	}
}

public class hamiltion {
	public static void main(String args[]) {
		int v;
		int[][] matrixs;
		matrixs = new int[200][200]; // 输入为二维邻接矩阵
		Scanner cin = new Scanner(System.in);
		System.out.println("下面判断一个连通图是不是汉密尔顿图");
		System.out.println("请输入结点个数：");
		v = cin.nextInt();
		System.out.println("请输入该简单图的邻接矩阵：");
		for (int i = 0; i <= v; i++) {

			for (int j = 0; j <= v; j++) {
				if (i == 0 || j == 0)
					continue;
				else
					matrixs[i][j] = cin.nextInt();
			}
		}
		gethamiltion h = new gethamiltion();
		Boolean p;
		Boolean q = h.quickcheck(matrixs, v);
		if (q == true) {
			System.out.println("此图是汉密尔顿图！");
			System.out.println("其中一个汉密尔顿回路为:");
			{
				for (int i = 1; i <= v; i++) {

					if (i == 1) {
						System.out.print(i);
						continue;
					}
					System.out.print("->" + i);
				}
				System.out.println("->" + 1);
			}
		} else {
			p = h.dfshamiltion(matrixs, 1, 1, v);
			if (p == true) {
				System.out.println("此图是汉密尔顿图！");
				int i;
				System.out.println("汉密尔顿回路如下：");
				for (i = 2; i <= v + 1; i++) {
					if (i == 2) {
						System.out.print(h.loop[i]);
						continue;
					}
					System.out.print("->" + h.loop[i]);
				}
				System.out.println("->" + 1);
			} else if (p == false)
				System.out.println("此图不是汉密尔顿图！");

		}
	}
}

文档说明：

测试用例：

运行结果：
下面判断一个连通图是不是汉密尔顿图
请输入结点个数：
3
请输入该简单图的邻接矩阵：
0 1 1
1 0 1
1 1 0
此图是汉密尔顿图！
汉密尔顿回路如下：
1->2->3->1

运行结果：
下面判断一个连通图是不是汉密尔顿图
请输入结点个数：
4
请输入该简单图的邻接矩阵：
0 1 0 0
1 0 1 1
0 1 0 0
0 1 0 0
此图不是汉密尔顿图！

//代码有借鉴的部分，具体链接已经没法找到，侵删。