上海制作网站公司网站,外贸建站seo优化,靖江有帮助做苏宁易购网站的公司吗,清洁公司网站建设输入#xff1a;有N个节点的无向图#xff0c;每个节点被标注为0#xff0c;1#xff0c;…N-1。graph[i][j]表示从节点i到节点j有一条边。 输出#xff1a;每个节点都访问一次#xff0c;至少需要几步。 规则#xff1a;可以重复访问一个节点。 分析#xff1a;这道题…输入有N个节点的无向图每个节点被标注为01…N-1。graph[i][j]表示从节点i到节点j有一条边。 输出每个节点都访问一次至少需要几步。 规则可以重复访问一个节点。 分析这道题目看了2个星期。其实这两周也是因为加班没有再看新的题目。在地铁上没事就把官方的解法方式拿出来看看。发现另有感悟。体会到了书读百遍其义自见。 我们需要返回沿着边走完N个节点需要几步。因为我们可以从任意一个节点开始走。所以我们可以先问从节点0开始走几步能访问了所有的节点。如果我们知道这个答案那么我们分别计算从0,1,2…N-1开始需要几步。取最小值就是答案。 输入示例[[1,2,3],[0],[0],[0]] 先计算从一个节点开始。假设从节点0开始。可能的路径节点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访问了节点03访问了节点0和12访问了节点1… 2N−12^N-12N−1访问了所有节点。
节点标签N-1N-2…3210代表值2N−12^{N-1}2N−12N−22^{N-2}2N−2…232^323222^222212^121202^020public 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;QueueState queue new LinkedList();int[][] dist new int[1N][N];for (int[] row: dist) Arrays.fill(row, N*N);int startNode 1;dist[1startNode][startNode] 0;queue.offer(new State(1startNode,startNode));//BFS遍历while(!queue.isEmpty()){int size queue.size();for(int i0;isize;i){State node queue.poll();int d dist[node.cover][node.head];if(node.cover (1N)-1) return d;for(int child : graph[node.head]){int newCover node.cover | 1 child;if(dist[newCover][child]d1){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[1N][N];for (int[] row: dist) Arrays.fill(row, N*N);int startNode 0;dist[1startNode][startNode] 0;dfs(new State(1startNode,startNode),graph,N,dist);return minDis;}private void dfs(State state,int[][] graph,int N,int[][] dist) {if(state.cover (1N)-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[1startNode][startNode] 0;queue.offer(new State(1startNode,startNode));修改为
for(int startNode0;startNodeN;startNode){dist[1startNode][startNode] 0;queue.offer(new State(1startNode,startNode));}代码
