c - 如何修改 BFS 算法以在给定条件下找到 2 个顶点之间的路径?
问题描述
我刚开始学习图表并陷入了这个问题。我试图找到图的两个顶点之间的最短路径(最小边数),条件是在路径的每 2 个中间顶点之间有 2 条替代路径(不计算长度)。
这是我的 BFS 算法。颜色的意思:
白色 = 尚未到达
灰色 = 到达的顶点将保持该颜色,直到无法到达他的所有邻居
黑色 = 到达顶点
pi[]
包含当前顶点的父节点
void bfs(int s)
{
int i;
for (i=1; i<=v; i++)
{
if (i != s)
{
color[i] = WHITE;
d[i] = INFTY;
pi[i] = NIL;
}
}
color[s] = GRAY;
d[s] = 0;
pi[s] = NIL;
queueInit(&q);
queuePush(&q,s);
while (!queueEmpty(&q))
{
int u = queueFront(&q);
int j;
for (j=1; j<=adj[u][0]; j++)
{
int x = adj[u][j];
if (color[x] == WHITE)
{
color[x] = GRAY;
d[x] = d[u]+1;
pi[x] = u;
queuePush(&q,x);
}
}
queuePop(&q);
color[u] = BLACK;
}
}
请帮助我更改算法以找到给定条件下的最短路径,或者至少给我一个建议!
解决方案
如果您开始调试代码,您会发现其中一个问题是节点在循环到其相邻节点之前没有弹出,所以毕竟算法在它们上再次运行,并且一些节点在算法之前弹出在他们身上运行。
我也不明白 line for (j=1; j<=adj[u][0]; j++)
,它在相邻顶点上循环。
来自cp-algorithms的 BFS 算法的实现:
vector<vector<int>> adj; // adjacency list representation
int n; // number of nodes
int s; // source vertex
queue<int> q;
vector<bool> used(n);
vector<int> d(n), p(n);
q.push(s);
used[s] = true;
p[s] = -1;
while (!q.empty()) {
int v = q.front();
q.pop(); // The node should be poped before looping on it's adjacent nodes
for (int u : adj[v]) {
if (!used[u]) {
used[u] = true;
q.push(u);
d[u] = d[v] + 1;
p[u] = v;
}
}
}
然后,假设我们要打印最短路径:
if (!used[u]) {
cout << "No path!";
} else {
vector<int> path;
for (int v = u; v != -1; v = p[v])
path.push_back(v);
reverse(path.begin(), path.end());
cout << "Path: ";
for (int v : path)
cout << v << " ";
}
推荐阅读
- php - Laravel 8.x - 将数据透视表数据传递给可邮寄
- javascript - 单击jQuery的Ajax更新发布请求
- flutter - 当我尝试更新用户配置文件时,我不断收到调用 null 的 getter
- javascript - Ajax、jQuery 和 Js,错误 500 代码中断
- netsuite - 在 Netsuite 中如何使用 php 获取税表?
- javascript - Node jS express 验证 facebook API
- python - Django:在 HTML 表单提交上调用 views.py 中的函数
- python - 如何在主进程中获得信号以启动操作?
- proxy - 通过本地机器代理/隧道访问VPN
- algorithm - 如何找到完成 n 个作业的最少处理器数