輸入：有N個節點的無向圖，每個節點被標注為0，1，…N-1。graph[i][j]表示從節點i到節點j有一條邊。
輸出：每個節點都訪問一次，至少需要幾步。
規則：可以重復訪問一個節點。
分析：這道題目看了2個星期。其實這兩周也是因為加班，沒有再看新的題目。在地鐵上沒事，就把官方的解法方式拿出來看看。發現另有感悟。體會到了書讀百遍其義自見。
　我們需要返回沿著邊走完N個節點需要幾步。因為我們可以從任意一個節點開始走。所以我們可以先問從節點0開始，走幾步能訪問了所有的節點。如果我們知道這個答案，那么我們分別計算從0,1,2…N-1開始，需要幾步。取最小值就是答案。
　輸入示例：[[1,2,3],[0],[0],[0]]
　先計算從一個節點開始。假設從節點0開始?？赡艿穆窂?#xff1a;節點0->節點1->？，之后需要再經過節點0，才有出路。我認為這道題目難的地方在于，之前為了防止重復訪問，一個元素被訪問之后做個標記，就可以。但是這里不可以。節點0->節點1->節點0->?如果此時再訪問節點1，那就進入死循環了。既要一個節點訪問多次，又要防止進入死循環。那么這里去重的不是節點，而是訪問過的節點路徑。
　狀態1：節點0->節點1，訪問了節點0和1，當前節點是1。
　狀態2：節點0->節點1->節點0，也是訪問了節點0和1，當前節點是0。
　上面的兩種狀態，雖然都只有兩個節點被訪問，但是當前節點不同，那么能選擇的路徑就可以不同。所以狀態1和狀態2是不同的狀態，不能被放棄。
　狀態3：節點0->節點1->節點0->節點1，也是訪問了節點0和1，當前節點是1。描述完之后就發現狀態3和狀態1是一樣的。而狀態3的步數更多。所以狀態3是屬于重復狀態，需要放棄。
　之后的可能的狀態是：
　狀態4：節點0->節點1->節點0->節點2
　狀態5：節點0->節點1->節點0->節點2->節點0
　狀態6：節點0->節點1->節點0->節點2->節點0->節點3
　也就是說需要5步可以遍歷完所有節點。
　我們可以使用DFS或者BFS遍歷邊。編碼的重點是解決怎么記錄狀態。我們需要記錄當前已經訪問了哪些節點，當前節點是哪個。前者使用bit數組記錄。1=訪問了節點0；3=訪問了節點0和1；2=訪問了節點1… $2^N?1=$訪問了所有節點。

節點標簽N-1N-2…3210

代表值	$2^{N?1}$	$2^{N?2}$	…	$2^3$	$2^2$	$2^1$	$2^0$

public class ShortestPathVisitingAllNodesV2 {public static void main(String[] args){int[][] graph = new int[4][];graph[0] = new int[]{1,2,3};graph[1] = new int[]{0};graph[2] = new int[]{0};graph[3] = new int[]{0};int r = new ShortestPathVisitingAllNodesV2().shortestPathLengthDFS(graph);System.out.println(r);}public int shortestPathLengthBFS(int[][] graph) {int N = graph.length;Queue<State> queue = new LinkedList();int[][] dist = new int[1<<N][N];for (int[] row: dist) Arrays.fill(row, N*N);int startNode = 1;dist[1<<startNode][startNode] = 0;queue.offer(new State(1<<startNode,startNode));//BFS遍歷while(!queue.isEmpty()){int size = queue.size();for(int i=0;i<size;i++){State node = queue.poll();int d = dist[node.cover][node.head];if(node.cover == (1<<N)-1) return d;for(int child : graph[node.head]){int newCover = node.cover | 1 << child;if(dist[newCover][child]>d+1){dist[newCover][child] = d +1;queue.offer(new State(newCover,child));}}}}throw null;}private int minDis = Integer.MAX_VALUE;public int shortestPathLengthDFS(int[][] graph) {int N = graph.length;int[][] dist = new int[1<<N][N];for (int[] row: dist) Arrays.fill(row, N*N);int startNode = 0;dist[1<<startNode][startNode] = 0;dfs(new State(1<<startNode,startNode),graph,N,dist);return minDis;}private void dfs(State state,int[][] graph,int N,int[][] dist) {if(state.cover == (1<<N)-1){minDis = Math.min(minDis,dist[state.cover][state.head]);}else{for(int child : graph[state.head]){int newCover = state.cover | 1 << child;if(dist[newCover][child]>dist[state.cover][state.head]+1){dist[newCover][child] = dist[state.cover][state.head]+1;dfs(new State(newCover,child),graph,N,dist);}}}}class State {int cover, head;State(int c, int h) {cover = c;head = h;}} }

再進一步計算從各個節點開始。修改代碼

int startNode = 1;dist[1<<startNode][startNode] = 0;queue.offer(new State(1<<startNode,startNode));

修改為：

for(int startNode=0;startNode<N;startNode++){dist[1<<startNode][startNode] = 0;queue.offer(new State(1<<startNode,startNode));}

代碼

總結

以上是生活随笔為你收集整理的847. Shortest Path Visiting All Nodes（二）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。