我有一个未加权的有向图 G，它可能非常大(数千个节点)。
我有兴趣找到边数有限(路径最多包含 10 条边)的特定两个节点之间的所有可能路径(无循环)。有没有可以处理这个大图的快速算法。
最佳答案
可以修改dfs来解决这个问题。只需添加另一个参数 - 您当前所在的深度，如果在目标节点 target 之前达到路径长度限制，则切断 dfs .为了演示我将使用递归实现的想法，我将使用全局数组 used - 节点在途中访问了这么远。此外，我将假设我们已经使用邻域列表表示法存储了图形(我们称之为 neList，节点 v 的邻居位于 neList[v]):
used[n] = {false}
neList; // neighborhoodList
limit = 10 // max path len
void dfs(int v, int depth) {
if (depth == limit) {
if (v == target) {
print_path
} else {
return
}
}
for u in neList[v] {
if (used[u]) {
continue;
}
used[u] = true
dfs(u, depth + 1)
used[u] = false
}
}
您可以稍微优化此方法 - 首先从目标节点执行 bfs 以计算 target 之间的最小距离和所有节点。在dfs只去找邻居u如果depth + min_dist[u] <= limit .
关于algorithm - 具有有限边数的未加权无向图中两个节点之间的所有路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26847797/