从源到宿的步行次数,精确到h跳

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

给出一个无向图,一个起始顶点和一个终止顶点。查找从源到接收器的恰好涉及h个跃点的步行数(这样一个顶点可以被多次访问)。例如,如果图形是三角形,则具有第h个跃点的此类路径数由第h个Jakobstahl number给出。可以将其扩展为完全连接的k节点图,从而产生递归(和闭式解)here

[当图形是n边多边形时,可接受的答案here将走数表示为二项式项的总和。

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

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

algorithm graph big-o breadth-first-search
3个回答
3
投票

3
投票

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