目录一哈密顿回路、哈密顿链路二相关定理1Dirac定理2Tutte定理3竞赛图必有哈密顿链路三应用1旅行商问题TSP2芯片通孔四相关puzzle1数字满格、数阵迷踪、数字迷途、数字连线2踏马、立方骑士3矩形图中马的哈密顿回路、链路五点的回路覆盖问题1回路覆盖问题2相关定理3应用六最短哈密顿链路1不指定起点和终点2只指定起点3只指定终点4指定起点和终点5汇总模板6力扣实战模板力扣 943. 最短超级串不指定起点和终点力扣 LCP 13. 寻宝指定起点和终点7力扣实战非模板力扣 996. 正方形数组的数目力扣 980. 不同路径 III一哈密顿回路、哈密顿链路图的哈密顿回路是指包含图的所有节点的回路。图的哈密顿链路是指包含图的所有节点的链路。二相关定理1Dirac定理如果G是一个nn≥3个点的无向简单图所有节点的度数都 ≥ n/2.0则G中存在哈密顿回路。证明过程1G是连通图2设最长路径是L用抽屉原理可以证明L是个环3如果有节点不在环中根据连通性可以加入一个点把环变成一条更长的路径。所以所有节点都在这个环中。2Tutte定理所有4连通平面图都有哈密顿圈。证明过程没研究。关于平面图参考常见的图3竞赛图必有哈密顿链路关于竞赛图参考常见的图竞赛图中不存在环当且仅当所有顶点的出度从小到大排列依次为0, 1, 2, … , n-1 。翻译成赛事语言就是单循环赛结果没有环当且仅当所有人的实力是线性排序的没有任何一次比赛发生逆袭现象。三应用1旅行商问题TSP给定一系列城市和每对城市之间的距离求解访问每一座城市一次并回到起始城市的最短回路。这是NP难问题。2芯片通孔芯片上有很多不同尺寸的通孔用于走线。同一尺寸的通孔用1个钻头全部打完之后再换钻头。对于1个钻头来说如何走最短的距离把所有通孔打完四相关puzzle1数字满格、数阵迷踪、数字迷途、数字连线数字满格、数阵迷踪、数字迷途、数字连线2踏马、立方骑士踏马、立方骑士3矩形图中马的哈密顿回路、链路定理如果n是偶数n4那么n*n的棋盘有一个哈密顿回路。如果n是奇数n3那么n*n的棋盘有一个哈密顿链路。像这样的图还可以构造一些不过基本上都差不多。总结起来就是最中间的格子是比较特殊的上图中标号1-8的这8个格子构成1个回路其余的16个格子也构成1个回路相当于5*5的棋盘其实就是3个回路组合而成只要适当地选择断点即可把3个回路连接成一条链。如果选取的起点不同得到的哈密顿链还是略有区别的。比如112象棋12关于上面的2个定理书上的意思是用数学归纳法来证明从nk变成nk4相当于在原来的基础上套上了一个宽度为2的边框。这个边框是若干个哈密顿回路组成的只要在适当的地方断开就可以和里面的k*k连接起来。下面讨论7*7的棋盘去掉中间的3*3如何形成哈密顿回路。首先角落的点只有2个邻居那么在回路里面这2个点也一定都是他的邻居。其他的以此类推可以得到下图对于那些已经连了2条线的点自然是没有任何悬念了所以接下来只需要考虑那些恰好连了1条线的点该如何连接起来。将上图化简如下黑色的线表示一定相连红色的线表示可能相连。这样可以得到这16个点的哈密顿回路与此对应可以得到原图这是由2个哈密顿回路构成的。这样整个通过把大的回路断开一个地方可以得到下图在把紫色的哈密顿回路和这个长为41的哈密顿链连接起来即可得到7*7的哈密顿链五点的回路覆盖问题1回路覆盖问题对于没有割边的图求一组简单回路覆盖所有的点且总边数最少。2相关定理n个点的无割边图存在一组简单回路覆盖所有的点且总边数不超过2n-23应用如果按照这个方式建设网络就能得到边数很少的无割边图。无割边意味着至少是2连通比普通的连通图稳定性更好。六最短哈密顿链路对于有向图求所有的哈密顿链路中长度最短的那条。1不指定起点和终点思路状态压缩DP时间复杂度On^2 * 2^n//最短哈密顿链路 templatetypename T int class MinHamilton { public: MinHamilton(int n, DirectedGraphDataT g) :g(g) //n的上限大概是15 { this-n n; startId g.getStartId(); m.clear(); path.clear(); } vectorint getMinPath() //返回0到n-1的排序 { int allId (1 n) - 1; int ans INT_MAX; for (int i 0; i n; i) { ans min(ans, dp(i, allId ^ (1 i))); } for (int i 0; i n; i) { if (m[i][allId ^ (1 i)] ans) { reBuild(i, allId ^ (1 i), ans); return path; } } return vectorint{}; } private: int dp(int id, int allOtherId) { auto mi m[id]; if (mi.find(allOtherId) ! mi.end())return mi[allOtherId]; if (!allOtherId)return mi[allOtherId] 0; int ans INT_MAX; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; int x dp(i, allOtherId ^ (1 i)); if (x INT_MAX)ans min(ans, x it-second); } return mi[allOtherId] ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId)return; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 i)] ans - it-second) { return reBuild(i, allOtherId ^ (1 i), ans - it-second); } } } private: DirectedGraphDataT g; int n; int startId; mapint, mapint, intm; vectorintpath; };2只指定起点//最短哈密顿链路 templatetypename T int class MinHamilton { public: MinHamilton(int n, DirectedGraphDataT g, int startLoc) :g(g) //n的上限大概是15 { this-n n; startId g.getStartId(); this-startLoc startLoc - startId; m.clear(); path.clear(); } vectorint getMinPath() //返回0到n-1的排序 { int allId (1 n) - 1; int ans dp(startLoc, allId ^ (1 startLoc)); reBuild(startLoc, allId ^ (1 startLoc), ans); return path; } private: int dp(int id, int allOtherId) { auto mi m[id]; if (mi.find(allOtherId) ! mi.end())return mi[allOtherId]; if (!allOtherId)return mi[allOtherId] 0; int ans INT_MAX; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; int x dp(i, allOtherId ^ (1 i)); if (x INT_MAX)ans min(ans, x it-second); } return mi[allOtherId] ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId)return; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 i)] ans - it-second) { return reBuild(i, allOtherId ^ (1 i), ans - it-second); } } } private: DirectedGraphDataT g; int n; int startId; int startLoc; mapint, mapint, intm; vectorintpath; };3只指定终点把起点和终点互换把图变成反图即可转化成只指定起点的场景。4指定起点和终点//最短哈密顿链路 templatetypename T int class MinHamilton { public: MinHamilton(int n, DirectedGraphDataT g, int startLoc,int targetLoc) :g(g) //n的上限大概是15 { this-n n; startId g.getStartId(); this-startLoc startLoc - startId; this-targetLoc targetLoc - startId; m.clear(); path.clear(); } vectorint getMinPath(int ans) //返回0到n-1的排序 { int allId (1 n) - 1; ans dp(startLoc, allId ^ (1 startLoc) ^ (1 targetLoc)); reBuild(startLoc, allId ^ (1 startLoc) ^ (1 targetLoc), ans); return path; } private: int dp(int id, int allOtherId) { auto mi m[id]; if (mi.find(allOtherId) ! mi.end())return mi[allOtherId]; if (!allOtherId) { auto it g.edgeMap.find(make_pair(startId id, startId targetLoc)); if (it g.edgeMap.end())return mi[allOtherId] INT_MAX; return mi[allOtherId] it-second; } int ans INT_MAX; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; int x dp(i, allOtherId ^ (1 i)); if (x INT_MAX)ans min(ans, x it-second); } return mi[allOtherId] ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (!allOtherId) { path.push_back(targetLoc); return; } for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 i)] ans - it-second) { return reBuild(i, allOtherId ^ (1 i), ans - it-second); } } } private: DirectedGraphDataT g; int n; int startId; int startLoc; int targetLoc; mapint, mapint, intm; vectorintpath; };5汇总模板//最短哈密顿链路 templatetypename T int class MinHamilton { public: MinHamilton(int n, DirectedGraphDataT g) :g(g) //n的上限大概是15 { type 0; this-n n; startId g.getStartId(); } MinHamilton(int n, DirectedGraphDataT g, int startLoc) :g(g) //如果g的顶点编号是3-6则startLoc属于[3,6]且n4且startId3 { type 1; this-n n; startId g.getStartId(); this-startLoc startLoc - startId; } MinHamilton(int n, DirectedGraphDataT g, int startLoc,int targetLoc) :g(g) { type 2; this-n n; startId g.getStartId(); this-startLoc startLoc - startId; this-targetLoc targetLoc - startId; } vectorint getMinPath(int ans) //返回0到n-1的排序, ans是最短距离 { path.clear(); m.clear(); int allId (1 n) - 1; if (type 2) { ans dp(startLoc, allId ^ (1 startLoc) ^ (1 targetLoc)); reBuild(startLoc, allId ^ (1 startLoc) ^ (1 targetLoc), ans); } else if (type 1) { ans dp(startLoc, allId ^ (1 startLoc)); reBuild(startLoc, allId ^ (1 startLoc), ans); } else { ans INT_MAX; for (int i 0; i n; i) { ans min(ans, dp(i, allId ^ (1 i))); } for (int i 0; i n; i) { if (m[i][allId ^ (1 i)] ans) { reBuild(i, allId ^ (1 i), ans); break; } } } return path; } private: int dp(int id, int allOtherId) { auto mi m[id]; if (mi.find(allOtherId) ! mi.end())return mi[allOtherId]; if (type 2) { if (!allOtherId) { auto it g.edgeMap.find(make_pair(startId id, startId targetLoc)); if (it g.edgeMap.end())return mi[allOtherId] INT_MAX; return mi[allOtherId] it-second; } } else { if (!allOtherId)return mi[allOtherId] 0; } int ans INT_MAX; for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; int x dp(i, allOtherId ^ (1 i)); if (x INT_MAX)ans min(ans, x it-second); } return mi[allOtherId] ans; } void reBuild(int id, int allOtherId, int ans) { path.push_back(id); if (type 2) { if (!allOtherId) { path.push_back(targetLoc); return; } } else { if (!allOtherId)return; } for (int i 0; i n; i) { if ((allOtherId (1 i)) 0)continue; auto it g.edgeMap.find(make_pair(startId id, startId i)); if (it g.edgeMap.end())continue; if (m[i][allOtherId ^ (1 i)] ans - it-second) { return reBuild(i, allOtherId ^ (1 i), ans - it-second); } } } private: int type; // 0:不指定起点和终点 1:只指定起点 2:指定起点和终点 DirectedGraphDataT g; int n; int startId; int startLoc; int targetLoc; mapint, mapint, intm; vectorintpath; };6力扣实战模板力扣 943. 最短超级串不指定起点和终点给定一个字符串数组words找到以words中每个字符串作为子字符串的最短字符串。如果有多个有效最短字符串满足题目条件返回其中任意一个即可。我们可以假设words中没有字符串是words中另一个字符串的子字符串。示例 1输入words [alex,loves,leetcode]输出alexlovesleetcode解释alexlovesleetcode 的所有排列都会被接受。示例 2输入words [catg,ctaagt,gcta,ttca,atgcatc]输出gctaagttcatgcatc提示1 words.length 121 words[i].length 20words[i]由小写英文字母组成words中的所有字符串互不相同class Solution { public: string shortestSuperstring(vectorstring words) { if (words.size() 1)return words[0]; vectorDirectedEdge edges; for (int i 0; i words.size(); i) { for (int j 0; j words.size(); j) { if (i j)continue; edges.push_back(DirectedEdge{vectorint{i, j, -sameNum(words[i], words[j])}}); } } DirectedGraphData g(edges); MinHamilton opt(words.size(), g); auto v opt.getMinPath(); string ans words[v[0]]; for (int i 1; i v.size(); i) { int len sameNum(words[v[i - 1]], words[v[i]]); ans words[v[i]].substr(len, words[v[i]].length() - len); } return ans; } int sameNum(string s1, string s2) { int len min(s1.length(), s2.length()); for (int i len - 1; i; i--) { if (s1.substr(s1.length() - i, i) s2.substr(0, i))return i; } return 0; } };力扣 LCP 13. 寻宝指定起点和终点我们得到了一副藏宝图藏宝图显示在一个迷宫中存在着未被世人发现的宝藏。迷宫是一个二维矩阵用一个字符串数组表示。它标识了唯一的入口用 S 表示和唯一的宝藏地点用 T 表示。但是宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点用 M 表示只有所有机关均被触发才可以拿到宝藏。要保持机关的触发需要把一个重石放在上面。迷宫中有若干个石堆用 O 表示每个石堆都有无限个足够触发机关的重石。但是由于石头太重我们一次只能搬一个石头到指定地点。迷宫中同样有一些墙壁用 # 表示我们不能走入墙壁。剩余的都是可随意通行的点用 . 表示。石堆、机关、起点和终点无论是否能拿到宝藏也是可以通行的。我们每步可以选择向上/向下/向左/向右移动一格并且不能移出迷宫。搬起石头和放下石头不算步数。那么从起点开始我们最少需要多少步才能最后拿到宝藏呢如果无法拿到宝藏返回 -1 。示例 1输入 [S#O, M.., M.T]输出16解释最优路线为 S-O, cost 4, 去搬石头 O-第二行的M, cost 3, M机关触发 第二行的M-O, cost 3, 我们需要继续回去 O 搬石头。 O-第三行的M, cost 4, 此时所有机关均触发 第三行的M-T, cost 2去T点拿宝藏。 总步数为16。示例 2输入 [S#O, M.#, M.T]输出-1解释我们无法搬到石头触发机关示例 3输入 [S#O, M.T, M..]输出17解释注意终点也是可以通行的。限制1 maze.length 1001 maze[i].length 100maze[i].length maze[j].lengthS 和 T 有且只有一个0 M的数量 160 O的数量 40题目保证当迷宫中存在 M 时一定存在至少一个 O 。class Solution { public: int minimalSteps(vectorstring maze) { int s, t; //编号0,1 vectorint locM; //所有的M, 编号2,3... vectorint locO; //所有可达的O mapint, intlen; //起点S到其他点的最短距离 bfs(maze, s, t, locM, locO, len); if (locM.empty())return len[t] 0 ? -1 : len[t]; if (locO.empty())return -1; if (!checkMandT(locM,len,t))return -1; mapint, mapint, intm1; //任意M到其他点的最短距离 for (auto id : locM) { m1[id] bfs(maze, id); } //mapint, mapint, intm2; //任意O到其他点的最短距离 mapint, mapint, intm3; //任意M或O到任意M的途经O的最短距离 getM3(s,locM,locO,len,m1, m3); vectorDirectedEdgeint edges; for (int i 0; i locM.size(); i) { edges.push_back(vectorint{ 0, i 2 ,m3[s][locM[i]] }); for (int j i 1; j locM.size(); j) { edges.push_back(vectorint{ i 2, j 2, m3[locM[i]][locM[j]] }); edges.push_back(vectorint{ j 2, i 2, m3[locM[i]][locM[j]] }); } edges.push_back(vectorint{ i 2, 1, m1[locM[i]][t] }); } DirectedGraphDataint dg(edges); MinHamiltonint opt(locM.size() 2, dg, 0, 1); int ans; auto v opt.getMinPath(ans); return ans; } private: //获取5个出参的值 void bfs(vectorstring maze, int s, int t, vectorint locM, vectorint locO, mapint, intlen) { GridGraph g(maze.size(), maze[0].length()); vectorintv; for (int i 0; i maze.size(); i) { for (int j 0; j maze[i].length(); j) { if (maze[i][j] S)s g.gridId(i, j); if (maze[i][j] T)t g.gridId(i, j); if (maze[i][j] M)locM.push_back(g.gridId(i, j)); if (maze[i][j] O)v.push_back(g.gridId(i, j)); } } len bfs(maze, s); for (auto id : v) { if (len[id])locO.push_back(id); } } mapint, int bfs(vectorstring maze, int s) { mapint, intlen; queueintq; q.push(s); len[s] 0; int c maze[0].length(); GridGraph g(maze.size(), c); while (!q.empty()) { int id q.front(); q.pop(); auto nbor g.getNeighbor4(id); for (auto x : nbor) { if (maze[x/c][x%c] ! # len.find(x) len.end()) { len[x] len[id] 1; q.push(x); } } } return len; } bool checkMandT(vectorint locM, mapint, intlen, int t) { if (len[t] 0)return false; for(auto id:locM)if (len[id] 0)return false; return true; } void getM3(int s, vectorint locM, vectorint locO, mapint, intlen, mapint, mapint, intm1, mapint, mapint, intm3) { for (auto id : locM) { for (auto id2 : locM) { int minLen INT_MAX; for (auto id3 : locO) { minLen min(minLen, m1[id][id3] m1[id2][id3]); } m3[id][id2] minLen; } } int id s; for (auto id2 : locM) { int minLen INT_MAX; for (auto id3 : locO) { minLen min(minLen, len[id3] m1[id2][id3]); } m3[id][id2] minLen; } } };7力扣实战非模板哈密顿问题其实和TSP问题差不多是NP问题没有特别好的算法。回溯法class Hamilton { public: stackint hami;//哈密顿链路 Hamilton(int n, mapint, vectorint m, int type)//type0是无向图 1是有向图 { this-n n; this-m m; this-type type; for (int i 0; i n; i)dfs(i); } private: bool dfs(int k) { s.push(k); if (s.size() n) { hami s; return true; } for (auto nk : m[k]) { if (visit[k])continue; visit[k] 1; if (dfs(nk))return true; visit[k] 0; } s.pop(); return false; } int n; int type; mapint, vectorint m;//邻接表 mapint, intvisit; stackints; };力扣 996. 正方形数组的数目给定一个非负整数数组A如果该数组每对相邻元素之和是一个完全平方数则称这一数组为正方形数组。返回 A 的正方形排列的数目。两个排列A1和A2不同的充要条件是存在某个索引i使得 A1[i] ! A2[i]。示例 1输入[1,17,8]输出2解释[1,8,17] 和 [17,8,1] 都是有效的排列。示例 2输入[2,2,2]输出1提示1 A.length 120 A[i] 1e9vectorint gnums; class Hamilton { public: maplong long, intans; Hamilton(int n, mapint, vectorint m, int type)//type0是无向图 1是有向图 { this-n n; this-m m; this-type type; for (int i 0; i n; i)dfs(i,1); } private: bool dfs(int k,int deep) { if (visit[k])return false; long long h2 h; hash(k); if (hashVisit[h]) goto RET; hashVisit[h] 1; if (deep n) { ans[h] 1; h h2; return true; } visit[k] 1; for (auto nk : m[k]) { dfs(nk,deep1); } RET: visit[k] 0; h h2; return false; } void hash(int k) { h ((h * (gnums[k]123) 666) * 789)%1000000007; } int n; int type; mapint, vectorint m;//邻接表 mapint, intvisit; maplong long, inthashVisit; long long h 1234567; }; class Solution { public: int numSquarefulPerms(vectorint nums) { int n nums.size(); mapint, vectorintm; for (int i 0; i n; i)for (int j i 1; j n; j) { if (isSquare(nums[i] nums[j]))m[i].push_back(j), m[j].push_back(i); } gnums nums; return Hamilton(n, m, 0).ans.size(); } bool isSquare(int n) { int x sqrt(n); return x * x n; } };力扣 980. 不同路径 III在二维网格grid上有 4 种类型的方格1表示起始方格。且只有一个起始方格。2表示结束方格且只有一个结束方格。0表示我们可以走过的空方格。-1表示我们无法跨越的障碍。返回在四个方向上、下、左、右上行走时从起始方格到结束方格的不同路径的数目。每一个无障碍方格都要通过一次但是一条路径中不能重复通过同一个方格。示例 1输入[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]输出2解释我们有以下两条路径 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)示例 2输入[[1,0,0,0],[0,0,0,0],[0,0,0,2]]输出4解释我们有以下四条路径 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) 2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3) 3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3) 4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)示例 3输入[[0,1],[2,0]]输出0解释没有一条路能完全穿过每一个空的方格一次。 请注意起始和结束方格可以位于网格中的任意位置。提示1 grid.length * grid[0].length 20class Hamilton { public: maplong long, intans; Hamilton(int n, mapint, vectorint m, int type,int start,int e)//type0是无向图 1是有向图 { this-n n; this-m m; this-type type; this-e e; dfs(start,1); } private: bool dfs(int k,int deep) { if (visit[k])return false; long long h2 h; hash(k); if (hashVisit[h]) goto RET; hashVisit[h] 1; if (deep n) { ans[h] 1; h h2; return true; } visit[k] 1; for (auto nk : m[k]) { if (deep n - 1 nk e)continue; dfs(nk,deep1); } RET: visit[k] 0; h h2; return false; } void hash(int k) { h ((h * (k123) 666) * 789)%1000000007; } int n; int type; mapint, vectorint m;//邻接表 mapint, intvisit; maplong long, inthashVisit; long long h 1234567; int e; }; class Solution { public: int uniquePathsIII(vectorvectorint grid) { rowgrid.size(),col grid[0].size(); int n row*col; mapint, vectorintm; int s, e; for (int i 0; i row; i)for (int j 0; j col; j) { if (grid[i][j] -1) { n--; continue; } if (grid[i][j] 1)s id(i, j); if (grid[i][j] 2)e id(i, j); vectorint v getNeighbor4(id(i, j)); for (int k : v)if(grid[k/col][k%col]!-1)m[k].push_back(id(i, j)); } return Hamilton(n, m, 0,s,e).ans.size(); } int id(int x, int y) { return x * col y; } vectorint getNeighbor4(int k) { vectorintans; if (k col)ans.push_back(k - col); if (k (row - 1) * col)ans.push_back(k col); if (k % col)ans.push_back(k - 1); if (k % col col - 1)ans.push_back(k 1); return ans; } int row,col; };