从源到接收器的路径数,完全是$ h $跳数

问题描述 投票:2回答:3

给出一个无向图,一个起始顶点和一个终止顶点。查找从源到接收器的恰好涉及h个跃点的步行数(这样一个顶点可以被多次访问)。例如,如果图形是三角形,则具有第h个跃点的此类路径数由第h个Jakobstahl number给出。

我假设可能有一种有效的算法来为任何给定的图找到该数字?我们可以假设该图以邻接矩阵或邻接列表或任何其他方便的符号表示。

给出一个无向图,一个起始顶点和一个终止顶点。查找从源到接收器的恰好涉及h个跃点的步行数(这样一个顶点可以被多次访问)。对于...

algorithm graph big-o breadth-first-search
3个回答
2
投票
2] log n)。但是,如果您要查找的数量不适合一个机器单词,那么这种方法的成本将取决于答案的大小,因为乘积会花费不同的时间。对于大多数图和小n来说,这不是问题,但是如果n大而图的其他部分紧密连接,则会放慢速度。

2
投票

1
投票
对于每个可能的路径,每个跃点都会减小该变量,并且当到达零时,您的算法将尝试使用另一条路径,并且如果在使变量达到零之前曾经到达目标,则该路径将被添加到您想要的路径
© www.soinside.com 2019 - 2024. All rights reserved.