数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++ 中访问所有节点的最短路径
假设我们有一个具有 N 个节点的无向连通图，这些节点标记为 0、1、2、...、N-1。图的长度将为 N，并且在列表 graph[i] 中，j 与 i 不相同，当且仅当节点 i 和 j 相连时。我们必须找到访问每个节点的最短路径的长度。我们可以从任何节点开始和停止，可以多次重新访问节点，并且可以重复使用边。
因此，如果输入类似于 [[1],[0,2,4],[1,3,4],[2],[1,2]]，则输出将为 4。现在，这里一条可能的路径是 [0,1,4,2,3]。
为了解决这个问题，我们将遵循以下步骤：
定义一个队列
n := 图的大小
req := 2^(n - 1)
定义一个映射
初始化 i := 0，当 i < n 时，更新（i 加 1），执行：
将 {0 OR (2^i), i} 插入 q
如果 n 等于 1，则：
返回 0
初始化 lvl := 1，当 q 不为空时，更新（lvl 加 1），执行：
sz := q 的大小
当 sz 不为零时，每次迭代 sz 减 1，执行：
定义一个数组 curr = q 的首元素
从 q 中删除元素
初始化 i := 0，当 i < graph[curr[1]] 的大小时，更新（i 加 1），执行：
u := graph[curr[1], i]
newMask := (curr[0] OR 2^u)
如果 newMask 等于 req，则：
返回 lvl
如果调用 visited[u] 的 count(newMask)，则：
忽略以下部分，跳过到下一次迭代
将 newMask 插入 visited[u]
将 {newMask, u} 插入 q
返回 -1
让我们看看以下实现以获得更好的理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
int shortestPathLength(vector<vector<int> >& graph){
queue<vector<int> > q;
int n = graph.size();
int req = (1 << n) - 1;
map<int, set<int> > visited;
for (int i = 0; i < n; i++) {
q.push({ 0 | (1 << i), i });
}
if (n == 1)
return 0;
for (int lvl = 1; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
vector<int> curr = q.front();
q.pop();
for (int i = 0; i < graph[curr[1]].size(); i++) {
int u = graph[curr[1]][i];
int newMask = (curr[0] | (1 << u));
if (newMask == req)
return lvl;
if (visited[u].count(newMask))
continue;
visited[u].insert(newMask);
q.push({ newMask, u });
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1},{0,2,4},{1,3,4},{2},{1,2}};
cout << (ob.shortestPathLength(v));
}输入
{{1},{0,2,4},{1,3,4},{2},{1,2}}输出
4
更新于: 2020-06-04
1K+ 浏览量
广告