网站后期,编程培训机构排名前十,wordpress新用户下载权限,网站开发和优化关系本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 存在一个由 n 个节点组成的无向连通图图中的节点按从 0 到 n - 1 编号。
给你一个数组 graph 表示这个图。其中graph[i] 是一个列表由所有与节点 i 直接相连的节点组成。
返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止也可以多次重访节点并且可以重用边。
示例 1
输入graph [[1,2,3],[0],[0],[0]]
输出4
解释一种可能的路径为 [1,0,2,0,3]示例 2 输入graph [[1],[0,2,4],[1,3,4],[2],[1,2]]
输出4
解释一种可能的路径为 [0,1,4,2,3]提示
n graph.length1 n 120 graph[i].length ngraph[i] 不包含 i如果 graph[a] 包含 b 那么 graph[b] 也包含 a输入的图总是连通图 解法1 状态压缩 广度优先搜索
由于题目需要我们求出「访问所有节点的最短路径的长度」并且图中每一条边的长度均为 1 1 1 因此我们可以考虑使用广度优先搜索的方法求出最短路径。
在常规的广度优先搜索中我们会在队列中存储节点的编号。对于本题而言最短路径的前提是「访问了所有节点」因此除了记录节点的编号以外我们还需要记录每一个节点的经过情况。因此我们使用三元组 ( u , m a s k , d i s t ) (u, mask,dist) (u,mask,dist) 表示队列中的每一个元素其中 u u u 表示当前位于的节点编号 m a s k mask mask 是一个长度为 n n n 的二进制数表示每一个节点是否经过。如果 m a s k mask mask 的第 i i i 位是 1 1 1 则表示节点 i i i 已经过否则表示节点 i i i 未经过 d i s t dist dist 表示到当前节点为止经过的路径长度。
这样一来我们使用该三元组进行广度优先搜索即可解决本题。初始时我们将所有的 ( i , 2 i , 0 ) (i,2^i,0) (i,2i,0) 放入队列表示可以从任一节点开始。在搜索的过程中如果当前三元组中的 m a s k mask mask 包含 n n n 个 1 1 1即 mask 2 n − 1 \textit{mask} 2^n - 1 mask2n−1 那么我们就可以返回 d i s t dist dist 作为答案。
细节为了保证广度优先搜索时间复杂度的正确性即同一个节点 u u u 以及节点的经过情况 m a s k mask mask 只被搜索到一次我们可以使用数组或者哈希表记录 ( u , m a s k ) (u,mask) (u,mask) 是否已经被搜索过防止无效的重复搜索。
class Solution {
public:int shortestPathLength(vectorvectorint g) {int n g.size();queuetupleint, int, int q;vectorvectorbool vis(n, vectorbool(1 n)); // [u,mask],避免重复遍历for (int i 0; i n; i) {q.emplace(i, 1 i, 0);vis[i][1 i] true;}int ans 0;while (!q.empty()) {auto [u, mask, dist] q.front();q.pop();if (mask (1 n) - 1) {ans dist;break;}// 搜索相邻的节点for (int v : g[u]) {// 将mask的第v位置1int maskV mask | (1 v);if (!vis[v][maskV]) {q.emplace(v, maskV, dist 1);vis[v][maskV] true;}}}return ans;}
};复杂度分析
时间复杂度 O ( n 2 ⋅ 2 n ) O(n^2 \cdot 2^n) O(n2⋅2n) 。常规的广度优先搜索的时间复杂度为 O ( n m ) O(nm) O(nm) 其中 n n n 和 m m m 分别表示图的节点数和边数。本题中引入了 m a s k mask mask 这一维度其取值范围为 [ 0 , 2 n ) [0, 2^n) [0,2n) 因此可以看成是进行了 2 n 2^n 2n 次常规的广度优先搜索。由于 m m m 的范围没有显式给出在最坏情况下为完全图有 O ( n 2 ) m O(n^2)m O(n2)m 因此总时间复杂度为 O ( n 2 ⋅ 2 n ) O(n^2 \cdot 2^n) O(n2⋅2n) 。空间复杂度 O ( n ⋅ 2 n ) O(n \cdot 2^n) O(n⋅2n) 即为队列需要使用的空间。 解法2 预处理点对间最短路 状态压缩动态规划
由于题目中给定的图是连通图那么我们可以计算出任意两个节点之间 u , v u, v u,v 间的最短距离记为 d ( u , v ) d(u,v) d(u,v) 。这样一来我们就可以使用动态规划的方法计算出最短路径。
对于任意一条经过所有节点的路径它的某一个子序列可以不连续一定是 0 , 1 , ⋯ , n − 1 0, 1, \cdots, n - 1 0,1,⋯,n−1 的一个排列。我们称这个子序列上的节点为「关键节点」。在动态规划的过程中我们也是通过枚举「关键节点」进行状态转移的。
我们用 f [ u ] [ mask ] f[u][\textit{mask}] f[u][mask] 表示从任一节点开始到节点 u u u 为止并且经过的「关键节点」对应的二进制表示为 m a s k mask mask 时的最短路径长度。由于 u u u 是最后一个「关键节点」那么在进行状态转移时我们可以枚举上一个「关键节点」 v v v 即 f [ u ] [ mask ] min v ∈ mask , v ≠ u { f [ v ] [ mask \ u ] d ( v , u ) } f[u][\textit{mask}] \min_{v \in \textit{mask}, v \neq u} \big\{ f[v][\textit{mask}\backslash u] d(v, u) \big\} f[u][mask]v∈mask,vumin{f[v][mask\u]d(v,u)}
其中 mask \ u \textit{mask} \backslash u mask\u 表示将 m a s k mask mask 的第 u u u 位从 1 1 1 变为 0 0 0 后的二进制表示。也就是说「关键节点」 v v v 在 m a s k mask mask 中的对应位置必须为 1 1 1 将 f [ v ] [ mask \ u ] f[v][\textit{mask} \backslash u] f[v][mask\u] 加上从 v v v 走到 u u u 的最短路径长度为 d ( v , u ) d(v,u) d(v,u) 取最小值即为 f [ u ] [ m a s k ] f[u][mask] f[u][mask] 。
最终的答案即为 min u f [ u ] [ 2 n − 1 ] \min_u f[u][2^n - 1] uminf[u][2n−1] 细节当 m a s k mask mask 中只包含一个 1 1 1 时我们无法枚举满足要求的上一个「关键节点」 v v v 。这里的处理方式与方法一中的类似若 m a s k mask mask 中只包含一个 1 1 1 说明我们位于开始的节点还未经过任何路径因此状态转移方程直接写为 f [ u ] [ m a s k ] 0 f[u][mask]0 f[u][mask]0 此外在状态转移方程中我们需要多次求出 d ( v , u ) d(v, u) d(v,u) 因此我们可以考虑在动态规划前将所有的 d ( v , u ) d(v,u) d(v,u) 预处理出来。这里有两种可以使用的方法时间复杂度均为 O ( n 3 ) O(n^3) O(n3)
我们可以使用 F l o y d Floyd Floyd 算法求出所有点对之间的最短路径长度我们可以进行 n n n 次广度优先搜索第 i i i 次从节点 i i i 出发也可以得到所有点对之间的最短路径长度。
class Solution {
public:int shortestPathLength(vectorvectorint g) {int n g.size();vectorvectorint d(n, vectorint(n, n 1));for (int i 0; i n; i) for (int j : g[i]) d[i][j] 1;// 使用floyd算法预处理出所有点对之间的最短路径长度for (int k 0; k n; k)for (int i 0; i n; i)for (int j 0; j n; j)d[i][j] min(d[i][j], d[i][k] d[k][j]);vectorvectorint f(n, vectorint(1 n, INT_MAX / 2));for (int mask 1; mask (1 n); mask) {// 如果mask只包含一个1即是2的幂if ((mask (mask - 1)) 0) {int u __builtin_ctz(mask);f[u][mask] 0; // 从某一点开始到u为止,经过的关键节点对应的二进制表示为mask时的最短路径长度} else {for (int u 0; u n; u) {if (mask (1 u)) { // 如果经过了点ufor (int v 0; v n; v) { // 枚举上一个关键节点if ((mask (1 v)) u ! v)f[u][mask] min(f[u][mask], f[v][mask ^ (1 u)] d[v][u]);}}}}}int ans INT_MAX;for (int u 0; u n; u) ans min(ans, f[u][(1 n) - 1]);return ans;}
};复杂度分析
时间复杂度 O ( n 2 ⋅ 2 n ) O(n^2 \cdot 2^n) O(n2⋅2n) 。状态的总数为 O ( n ⋅ 2 n ) O(n \cdot 2^n) O(n⋅2n) 对于每一个状态我们需要 O ( n ) O(n) O(n) 的时间枚举 v v v 进行状态转移因此总时间复杂度 O ( n 2 ⋅ 2 n ) O(n^2 \cdot 2^n) O(n2⋅2n) 。预处理所有 d ( u , v ) d(u, v) d(u,v) 的时间复杂度为 O ( n 3 ) O(n^3) O(n3) 但其在渐近意义下小于 O ( n 2 ⋅ 2 n ) O(n^2 \cdot 2^n) O(n2⋅2n) 因此可以忽略。空间复杂度 O ( n ⋅ 2 n ) O(n \cdot 2^n) O(n⋅2n) 即为存储所有状态需要使用的空间。
