n
组路径计算, n
位二进制标识 走法. 根据graph, 可以得到所有从节点 i
出发的相邻节点, 检查能到的下一个节点,
pub fn shortest_path_length(graph: Vec<Vec<i32>>) -> i32 {
use std::collections::VecDeque;
let n = graph.len();
let mut queue = VecDeque::new();
let mut visited = vec![vec![false; 1 << n]; n];
for i in 0..n {
// 从i节点开始搜索, 总过枚举n的起点
queue.push_back((i, 1 << i, 0));
visited[i][1 << i] = true; // 走法 1<<i 存一下
}
let mut ans = 0;
while !queue.is_empty() {
let (i, mask, dist) = queue.pop_front().unwrap();
if mask == (1 << n) - 1 {
// 全为1, 表示当前节点访问了所有其他节点
// 同时由于是 bfs, 因此先找到的必然最小, 即为结果
ans = dist;
break;
}
// 相邻节点
for e in graph.get(i).unwrap() {
let e = *e as usize;
// 将mask的第e位值为1, 更新状态
let mask_e = mask | (1 << e);
// 经过e的, 走法为 mask_e
if !visited[e][mask_e] {
// 下一步, 从e继续, 当前状态更新至 mask_e, 路径+1
queue.push_back((e, mask_e, dist + 1));
visited[e][mask_e] = true;
}
}
}
ans
}
时间复杂度 \(O(n^2 \cdot 2^n)\)
空间复杂度 \(O(n \cdot 2^n)\)