企业官网建设流程全解析

郑州制作网站软件,网站建设有何好处,新手制作网站,北京哪里能学做网站847. 访问所有节点的最短路径 问题描述 给你一个无向连通图#xff0c;包含 n 个节点#xff0c;编号从 0 到 n-1。给你一个二维数组 graph#xff0c;其中 graph[i] 是与节点 i 相连的节点列表。 返回访问所有节点的最短路径长度。你可以从任意节点开始和结束#xff0c;可…847. 访问所有节点的最短路径问题描述给你一个无向连通图包含n个节点编号从0到n-1。给你一个二维数组graph其中graph[i]是与节点i相连的节点列表。返回访问所有节点的最短路径长度。你可以从任意节点开始和结束可以多次访问同一节点和边。注意图是连通的任意两个节点之间都有路径节点数1 n 12可以重复访问节点和边示例输入:graph[[1,2,3],[0],[0],[0]]输出:4解释:一种最短路径是[1,0,2,0,3]输入:graph[[1],[0,2,4],[1,3,4],[2],[1,2]]输出:4解释:一种最短路径是[0,1,4,2,3]算法思路状态压缩BFS核心带状态的最短路径问题状态 (当前节点, 已访问的节点集合)由于 n ≤ 12可以用位掩码表示已访问的节点集合状态使用整数mask表示已访问的节点集合第i位为1表示节点i已访问状态 (node, mask)BFS从每个节点作为起点开始BFS队列存储(当前节点, 访问状态, 路径长度)目标状态mask (1 n) - 1所有节点都已访问去重使用visited[node][mask]避免重复访问相同状态求最短路径第一次到达某个状态就是最优的为什么用BFS而不是DFSBFS保证第一次到达目标状态时路径最短。代码实现importjava.util.*;classSolution{/** * 计算访问所有节点的最短路径长度 * 使用状态压缩BFS状态 (当前节点, 已访问节点的位掩码) * * param graph 无向连通图的邻接表 * return 访问所有节点的最短路径长度 */publicintshortestPathLength(int[][]graph){intngraph.length;// 特殊情况只有一个节点if(n1){return0;}// 目标状态所有n个节点都被访问inttargetMask(1n)-1;// visited[node][mask] 表示是否已经访问过状态(node, mask)boolean[][]visitednewboolean[n][1n];// BFS队列存储 [当前节点, 访问状态, 路径长度]Queueint[]queuenewLinkedList();// 初始化从每个节点开始BFSfor(inti0;in;i){intstartMask1i;// 只访问了节点iqueue.offer(newint[]{i,startMask,0});visited[i][startMask]true;}// BFS搜索while(!queue.isEmpty()){int[]currentqueue.poll();intnodecurrent[0];intmaskcurrent[1];intdistancecurrent[2];// 遍历当前节点的所有邻居for(intneighbor:graph[node]){// 更新访问状态将neighbor标记为已访问intnewMaskmask|(1neighbor);// 检查是否达到目标状态if(newMasktargetMask){returndistance1;}// 如果状态未访问过加入队列if(!visited[neighbor][newMask]){visited[neighbor][newMask]true;queue.offer(newint[]{neighbor,newMask,distance1});}}}return-1;}}算法分析时间复杂度O(n² × 2ⁿ)状态数量n个节点 × 2ⁿ种访问状态 O(n × 2ⁿ)每个状态需要遍历其所有邻居最多n个邻居总体O(n² × 2ⁿ)空间复杂度O(n × 2ⁿ)visited数组大小n × 2ⁿBFS队列最多存储 O(n × 2ⁿ) 个状态算法过程1graph [[1,2,3],[0],[0],[0]]图结构1 | 0 / \ 2 3BFS初始状态距离0(0, 0001),(1, 0010),(2, 0100),(3, 1000)距离1从0:(1, 0011),(2, 0101),(3, 1001)从1:(0, 0011)从2:(0, 0101)从3:(0, 1001)距离2从(1,0011):(0,0011)已访问从(2,0101):(0,0101)已访问从(3,1001):(0,1001)已访问从(0,0011):(2,0111),(3,1011)从(0,0101):(1,0111),(3,1101)从(0,1001):(1,1011),(2,1101)距离3从(2,0111):(0,0111)已访问从(3,1011):(0,1011)已访问从(1,0111):(0,0111)已访问从(3,1101):(0,1101)已访问从(1,1011):(0,1011)已访问从(2,1101):(0,1101)已访问距离4从(0,0111):(3,1111)→目标状态返回4从(0,1011):(2,1111)→目标状态返回4从(0,1101):(1,1111)→目标状态返回4结果4测试用例publicclassMain{publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例1星形图int[][]graph1{{1,2,3},{0},{0},{0}};System.out.println(Test 1: solution.shortestPathLength(graph1));// 4// 测试用例2复杂图int[][]graph2{{1},{0,2,4},{1,3,4},{2},{1,2}};System.out.println(Test 2: solution.shortestPathLength(graph2));// 4// 测试用例3两个节点int[][]graph3{{1},{0}};System.out.println(Test 3: solution.shortestPathLength(graph3));// 1// 测试用例4三个节点线性int[][]graph4{{1},{0,2},{1}};System.out.println(Test 4: solution.shortestPathLength(graph4));// 2// 测试用例5完全图3个节点int[][]graph5{{1,2},{0,2},{0,1}};System.out.println(Test 5: solution.shortestPathLength(graph5));// 2// 测试用例6单节点int[][]graph6{{}};System.out.println(Test 6: solution.shortestPathLength(graph6));// 0// 测试用例7四个节点环int[][]graph7{{1,3},{0,2},{1,3},{0,2}};System.out.println(Test 7: solution.shortestPathLength(graph7));// 3// 测试用例8链状图4个节点int[][]graph8{{1},{0,2},{1,3},{2}};System.out.println(Test 8: solution.shortestPathLength(graph8));// 3// 测试用例9复杂连通图int[][]graph9{{1,2,3,4},{0,2,3,4},{0,1,3,4},{0,1,2,4},{0,1,2,3}};System.out.println(Test 9: solution.shortestPathLength(graph9));// 2}}关键点状态压缩用位掩码表示集合处理访问过哪些节点问题多源BFS可以从任意节点开始需要将所有节点作为起点状态去重同一状态(node, mask)只需要访问一次重复访问不会产生更短的路径常见问题为什么不用Dijkstra算法所有边的权重都是1BFS就是最短路径算法。Dijkstra适用于带权重的图。