一：哈密爾頓回路與哈密爾頓路徑
1859 年咙边，愛爾蘭數(shù)學(xué)家哈密爾頓（Hamilton）提出了一個“周游世界”的游戲：
在一個正十二面體的二十個頂點(diǎn)上，標(biāo)注了倫敦扎附，巴黎第煮，莫斯科等世界著名大城市杜秸，正十二面體的棱表示連接著這些城市的路線放仗。要求游戲參與者從某個城市出發(fā)，把所有的城市都走過一次撬碟，且僅走過一次匙监，然后回到出發(fā)點(diǎn)。
簡而言之小作，哈密爾頓回路是指亭姥，從圖中的一個頂點(diǎn)出發(fā)，沿著邊行走顾稀，經(jīng)過圖的每個頂點(diǎn)达罗，且每個頂點(diǎn)僅訪問一次，之后再回到起始點(diǎn)的一條路徑静秆。如上圖所示粮揉，我們的起始點(diǎn)選定為 Washington DC，灰色實(shí)線構(gòu)成的一條路徑就是一條哈密爾頓回路抚笔。
在圖論算法的領(lǐng)域中扶认，哈密爾頓回路(Hamilton Loop)和路徑(Hamilton Path)在定義上是有所區(qū)分的：
哈密爾頓回路(Hamilton Loop)要求從起始點(diǎn)出發(fā)并能回到起始點(diǎn)，其路徑是一個環(huán)殊橙。
哈密爾頓路徑(Hamilton Path)并不要求從起始點(diǎn)出發(fā)能夠回到起始點(diǎn)辐宾，也就是說：起始頂點(diǎn)和終止頂點(diǎn)之間不要求有一條邊狱从。
譬如上面這兩個圖，左圖既存在哈密爾頓回路叠纹，也存在哈密爾頓路徑季研。而右圖只存在哈密爾頓路徑，并不存在哈密爾頓回路誉察。
二：求解哈密爾頓回路
如何求解一個圖是否存在哈密爾頓回路呢与涡？
一個最直觀的想法就是暴力求解。暴力求解的思路也很簡單：我們遍歷圖的每一個頂點(diǎn) v持偏，然后從頂點(diǎn) v 出發(fā)驼卖，看是否能夠找到一條哈密爾頓回路。
暴力求解的代價同求解全排列問題是等價的鸿秆，其時間復(fù)雜度為 酌畜，N 為圖的頂點(diǎn)的個數(shù)。
是一個非常高的復(fù)雜度谬莹，它并不是一個多項(xiàng)式級別的復(fù)雜度。像
桩了，
附帽，
這些我們常見的復(fù)雜度都是多項(xiàng)式級的復(fù)雜度，而
井誉，
這些復(fù)雜度是非多項(xiàng)式級的蕉扮，也就是說，在數(shù)據(jù)量 N 極大的情況下颗圣，我們的現(xiàn)代計算機(jī)是不能承受的喳钟。
那么除了暴力求解哈密爾頓回路問題，是否存在更好的算法在岂？
很遺憾的是奔则，對于哈密爾頓問題，目前并沒有多項(xiàng)式級別的算法蔽午。我們只能在暴力破解的基礎(chǔ)上易茬，盡量去做到更多的優(yōu)化，譬如回溯剪枝及老，記憶化搜索等抽莱，但是，還沒有找到一種多項(xiàng)式級別的算法來解決哈密爾頓問題骄恶。
通常食铐，這類問題也被稱為 NP(Non-deterministic Polynomial)難問題。
綜上所述僧鲁，求解哈密爾頓回路虐呻，我們可以采用回溯+剪枝的思想來進(jìn)行求解象泵。
對于這樣一個圖：
回溯+剪枝的過程模擬如下：
Java 代碼：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HamiltonLoop {
private Graph G;
private boolean[] visited;
private int[] pre;
private int end; // 用來表示最后一個被遍歷的頂點(diǎn)
public HamiltonLoop(Graph G) {
this.G = G;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
dfs(0, 0, G.V());
}
/**
* 對圖進(jìn)行深度優(yōu)先遍歷
*
* @param v
* @param parent
* @param left 表示還有多少個點(diǎn)沒有遍歷
* @return
*/
private boolean dfs(int v, int parent, int left) {
visited[v] = true;
pre[v] = parent;
left--;
// 如果所有的點(diǎn)遍歷完畢，并且起始點(diǎn)和終止點(diǎn)存在一條邊
if (left == 0 && G.hasEdge(0, v)) {
end = v;
return true;
}
// G.adj(v) 為尋找 v 的相鄰頂點(diǎn)
for (int w : G.adj(v))
if (!visited[w]) {
if (dfs(w, v, left)) return true;
}
visited[v] = false;
return false;
}
/**
* 獲取哈密爾頓回路
*
* @return
*/
public List<Integer> result() {
List<Integer> res = new ArrayList<>();
if (end == -1) return res;
int cur = end;
while (cur != 0) {
res.add(cur);
cur = pre[cur];
}
res.add(0);
Collections.reverse(res);
return res;
}
}
對于這兩個圖進(jìn)行測試铃慷，我的 HamiltonLoop 算法類輸出的結(jié)果如下：
圖1
[0, 1, 2, 3]
圖2
[]
因?yàn)閳D2 本身就不構(gòu)成一個哈密爾頓回路单芜，所以，其結(jié)果輸出為空也符合我們的意料之中犁柜。
三：求解哈密爾頓路徑
求解哈密爾頓路徑和求解哈密爾頓回路的算法整體框架是基本一致的洲鸠。
對于求解哈密爾頓路徑來說，起始點(diǎn)是誰很重要馋缅，同一個圖扒腕，從有的起始點(diǎn)出發(fā)就存在哈密爾頓路徑，從有的起始點(diǎn)出發(fā)就不存在哈密爾頓路徑萤悴。所以瘾腰，我們在算法設(shè)計中，構(gòu)造函數(shù)需要用戶顯示地傳入起始點(diǎn)覆履。
我的求解哈密爾頓路徑的算法類 HamiltonPath 的構(gòu)造函數(shù)是這樣的：
// 用戶需要在構(gòu)造器中傳入圖 G 以及起始點(diǎn) s
public HamiltonPath(Graph G,int s){
// ...
}
除了這一點(diǎn)外袁余，求解哈密爾頓路徑只需要保證，從起始點(diǎn)開始坷檩，所有的點(diǎn)均被遍歷到且僅被遍歷一次抄腔，并不需要起始點(diǎn)和終止點(diǎn)之間有邊。所以伟众，在 dfs 的邏輯中析藕，我們只需要改變遞歸的終止條件即可：
// 不需要保證終止點(diǎn) v 和 起始點(diǎn) s 存在一條邊，即： G.hasEdge(v, s)
if(left == 0 /*&& G.hasEdge(v, s)*/){
end = v;
return true;
}
整體的 Java 代碼如下：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class HamiltonPath {
private Graph G;
private int s;
private boolean[] visited;
private int[] pre;
private int end;
private int left;
public HamiltonPath(Graph G, int s) {
this.G = G;
this.s = s;
visited = new boolean[G.V()];
pre = new int[G.V()];
end = -1;
this.left = G.V();
dfs(s, s);
}
private boolean dfs(int v, int parent) {
visited[v] = true;
pre[v] = parent;
left--;
if (left == 0) {
end = v;
return true;
}
for (int w : G.adj(v)) {
if (!visited[w]) {
if (dfs(w, v)) return true;
}
}
visited[v] = false;
left++;
return false;
}
/**
* 返回哈密爾頓路徑
*
* @return
*/
public List<Integer> result() {
List<Integer> res = new ArrayList<>();
if (end == -1) return res;
int cur = end;
while (cur != s) {
res.add(cur);
cur = pre[cur];
}
res.add(s);
Collections.reverse(res);
return res;
}
}
依舊是對這兩個圖進(jìn)行測試凳厢，首先账胧，我們傳入構(gòu)造器的頂點(diǎn)設(shè)置為 0。我的 HamiltonPath 算法類輸出的結(jié)果如下：
圖一
[0, 1, 2, 3]
圖二
[0, 1, 2, 3]
從頂點(diǎn) 0 出發(fā)先紫，左右兩個圖均存在哈密爾頓路徑治泥。
然后，我們將傳入的頂點(diǎn)設(shè)置為 2遮精。我的 HamiltonPath 算法類輸出的結(jié)果如下：
圖一
[2, 1, 0, 3]
圖二
[]
左圖從頂點(diǎn) 2 出發(fā)存在哈密爾頓路徑车摄；右圖如果從頂點(diǎn) 2 出發(fā)，則不存在哈密爾頓路徑仑鸥，我們的算法結(jié)果輸出為空吮播，這與我們的預(yù)期結(jié)果是保持一致的。
四：狀態(tài)壓縮
在我們的代碼中眼俊，一直都使用布爾型的 visited 數(shù)組來記錄圖中的每一個頂點(diǎn)是否有被遍歷過意狠。在算法面試中，對于像哈密爾頓回路/路徑這樣的 NP 難問題疮胖，通常都會有輸入限制环戈，一般情況下闷板，求解問題中給定的圖不會超過 30 個頂點(diǎn)。
這樣院塞，在算法筆試/面試中遮晚，我們就可以對 visited 數(shù)組進(jìn)行狀態(tài)壓縮來優(yōu)化算法類執(zhí)行的效率。我們知道一個 int 型的數(shù)字有 32 位拦止，每一位不是 1 就是 0县遣，這正好對應(yīng)了布爾型的 true 和 false。
所以汹族，我們可以將 visited 數(shù)組簡化成一個數(shù)字萧求，該數(shù)字的每一個比特位用來表示 visited 數(shù)組的每一個 true 或 false 值。
來看一下我們的 HamiltonLoop 中 dfs 的代碼：
private boolean dfs(int v,int parent,int left) {
visited[v] = true; // 待優(yōu)化...
pre[v] = parent;
left--;
if(left == 0 && G.hasEdge(0,v)) {
end = v;
return true;
}
for(int w : G.adj(v))
if(!visited[w]) // 待優(yōu)化...
if(dfs(w,v,left)) return true;
visited[v] = false;
return false; // 待優(yōu)化...
}
我們的 dfs 中顶瞒，涉及到 visited 數(shù)組的操作共三處夸政，這三處我已經(jīng)使用注釋標(biāo)注出來了。
現(xiàn)在榴徐，我們的目標(biāo)就是使用一個數(shù)字來代替 visited 數(shù)組守问，如果 visited 是一個 int 型整數(shù)，那么這三處操作應(yīng)該如何用位運(yùn)算來表示呢坑资？
-
visited[v] = true;如果我們使用整型數(shù)字來表示 visited耗帕，那么這處的操作就是將數(shù)字的第 v 個位置從 0 設(shè)置為 1，其位運(yùn)算操作表示為：
visited + (1 << i) -
if(!visited[w])如果我們使用整型數(shù)字來表示 visited盐茎，那么這處的操作就是看數(shù)字的第 v 個位置是否為 0兴垦，其位運(yùn)算操作表示為：
(visited & (1 << i)) == 0 -
visited[v] = false;如果我們使用整型數(shù)字來表示 visited徙赢，那么這處的操作就是將數(shù)字的第 v 個位置從 1 設(shè)置為 0字柠，其位運(yùn)算操作表示為：
visited - (1 << i)
所以，我們的 HamiltonLoop 算法類中的 dfs 代碼改進(jìn)為：
private boolean dfs(int v,int parent,int left) {
visited += (1 << i); // 優(yōu)化
pre[v] = parent;
left--;
if(left == 0 && G.hasEdge(0,v)) {
end = v;
return true;
}
for(int w : G.adj(v))
if((visited & (1 << i)) == 0) // 優(yōu)化
if(dfs(w,v,left)) return true;
visited -= (1 << i)
return false; // 待優(yōu)化...
}
優(yōu)化后的 HamiltonLoop 類和 HamiltonPath 類的具體代碼請參考文章最后給出的鏈接狡赐。
五：LeetCode 980.不同路徑III
LeetCode 980 號問題是一個 <font color="red">Hard</font> 級別的圖論問題窑业。
題目鏈接：https://leetcode-cn.com/problems/unique-paths-iii/
題目信息:
在二維網(wǎng)格 grid 上，有四種類型的方格：
- 1 表示起始方格枕屉。且只有一個起始方格常柄。
- 2 表示結(jié)束方格，且只有一個結(jié)束方格搀擂。
- 0 表示我們可以走過的空方格西潘。
- -1 表示我們無法跨越的障礙。
返回在四個方向（上哨颂、下喷市、左、右）上行走時威恼，從起始方格到結(jié)束方格的不同路徑的數(shù)目品姓。
每一個無障礙方格都要通過一次寝并，但是一條路徑中不能重復(fù)通過同一個方格。
題目分析：
通過題目給定的條件腹备，我們知道衬潦，本題實(shí)際上就是一道標(biāo)準(zhǔn)的求解哈密爾頓路徑的問題。
和普通的求解哈密爾頓路徑不同植酥，題目中給定了四種類型的方格镀岛，值為 -1 的格子不能走，值為 0 的格子是可以走的惧互，并且 1 和 2 其實(shí)也屬于 0 這種類型的方格哎媚，雖然他們代表的含義是起始點(diǎn)和終點(diǎn)，但是本質(zhì)上來講和 0 沒什么區(qū)別喊儡，都是可以走的拨与。
所以，我們在進(jìn)行 dfs 回溯前艾猜，要先進(jìn)行預(yù)處理买喧。
第一個就是要更新我們的 left 變量。left 表示的含義是還有多少個頂點(diǎn)沒有遍歷匆赃，初始值為格子的數(shù)量淤毛。我們需要遍歷網(wǎng)格的每一個點(diǎn)，當(dāng)找到一個值為 -1 的網(wǎng)格就執(zhí)行一次 left-- 操作算柳。
第二個就是要將值為 1 和 2 的兩個格子的值變?yōu)?0低淡。并且，我們需要使用兩個變量來記錄原本值為 1 和 2 所在的格子的信息瞬项。具體做法為：遍歷 grid 二維網(wǎng)格蔗蹋，記錄值為 1 和 2 的格子，賦給變量 start 和 end囱淋，并在 grid 中將 1 和 2 的格子賦值為 0猪杭。
Java 代碼如下：
class Solution {
private int[][] grid;
private int r, c;
private int left;
private int start;
private int end;
private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
this.r = grid.length;
this.c = grid[0].length;
this.left = r * c;
int visited = 0;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (grid[i][j] == 1) {
start = i * c + j;
grid[i][j] = 0;
} else if (grid[i][j] == 2) {
end = i * c + j;
grid[i][j] = 0;
} else if (grid[i][j] == -1) {
left--;
}
return dfs(visited, start);
}
int dfs(int visited, int s) {
visited += (1 << s);
left--;
if (s == end && left == 0) {
// 回溯
visited -= (1 << s);
left++;
return 1;
}
int res = 0;
int x = s / c;
int y = s % c;
for (int d = 0; d < 4; d++) {
int nextX = x + dirs[d][0];
int nextY = y + dirs[d][1];
int next = nextX * c + nextY;
if (isValid(nextX, nextY) && (visited & (1 << next)) == 0 && grid[nextX][nextY] != -1) {
res += dfs(visited, next);
}
}
// 回溯
visited -= (1 << s);
left++;
return res;
}
private boolean isValid(int x, int y) {
return x >= 0 && x < r && y >= 0 && y < c;
}
}
六：總結(jié)
本篇文章，我介紹了哈密爾頓回路/路徑的概念妥衣，并且通過一道 LeetCode 題目皂吮，進(jìn)一步加深了我們對求解哈密爾頓回路/路徑的算法和回溯思想的理解。
最后税手，附上文章中的代碼所在倉庫地址：
https://github.com/jinrunheng/datastructure-and-algorithm
好啦蜂筹，至此為止，哈密爾頓回路/路徑我就介紹完畢了～歡迎大家關(guān)注我的公眾號【kim_talk】芦倒，在這里希望你可以收獲更多的知識艺挪，我們下一期再見！
