在给定起始顶点和深度限制的循环定向图中寻找所有可能的路径。

考虑下面给出的有向循环图,如果指定一个起点(例如:顶点0和允许的最大深度(例如:5),可以用什么算法来寻找所有可能的路径(注意:给定的顶点可以多次访问)?

enter image description here

如果指定一个起点(例如:顶点0)和一个允许的最大深度(例如:5),那么可以用什么算法来找到所有可能的路径(注意:一个给定的顶点可以被访问一次以上)?

实现这个图问题的最有效算法是什么?

下面给出了上述图的一些可能的路径,顺序不限(从顶点0开始,最大允许深度为5)。

  • 0 -> 1 -> 2 -> 4 -> 1 -> 3
  • 0 -> 1 -> 2 -> 4 -> 5 -> 1
  • 0->1->2->4->5->6。
  • 0 -> 1 -> 3 -> 5 -> 1 -> 3

解决方案:

伪算法,这将是一个增强的BFS,它一直跟踪它所经过的路径。当它达到要求的深度时,它就会记录路径,然后终止。

类似这样(node.js风格的语法)。

const requiredDepth = X
const relevantPaths = {}

const runBFS = (curNode, curPath = []) => {
    if (crPath.length === requiredDepth) {
        relevantPaths.push(curPath)
        return
    }

    for (let neighbor of curNode.neighbors) {
        const newPath = [ ...curPath, getEdge(curNode, neighbor) ]
        runBFS(neighbor, newPath)
    }
}

runBFS(root)

希望能帮到你

给TA打赏
共{{data.count}}人
人已打赏
解决方案

将十六进制数转换为2的补码。

2022-4-22 6:00:13

解决方案

Laravel Dompdf两列布局

2022-4-22 6:00:15

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索