algorithm - 从源到汇的步行次数正好是 h 跳

Question

给定一个无向图，一个起始顶点和一个结束顶点。求出从源到汇的步行次数(这样一个顶点可以被多次访问)正好涉及 h 跳。例如，如果图形是三角形，则具有 h 跳的此类路径的数量由第 h 个 Jakobstahl number 给出。 .这可以扩展到一个完全连接的 k 节点图，产生递归(和封闭形式的解决方案)here .

当图形是n边形时，接受的答案here将步行次数表示为二项式项的总和。

我假设可能有一个有效的算法来为任何给定的图找到这个数字？我们可以假设该图是以邻接矩阵或邻接表或任何其他方便的表示法提供的。

Answer 1

对此的解决方案是使用具有两个交替队列的修改后的 BFS 和一个针对特定长度的该节点路径的每个节点计数器:

paths(start, end, n):
    q = set(start)
    q_next = set()
    path_ct = map()
    path_ct_next = map()

    path_ct[start] = 1

    for i in [0, n):  # counting loop
        for node in q:  # queue loop
            for a in adjacent(node):  # neighbor-loop
                path_ct_next[a] += path_ct[node]
                q_next.add(a)

        q = q_next
        q_next = set()

        path_ct = path_ct_next
        path_ct_next = map()

   return path_ct_next[end]

这里的基本假设是 map() 生成一个字典，如果该条目尚不存在则返回零。否则它返回先前设置的值。计数循环只负责根据需要进行与跳数一样多的迭代。队列循环遍历可以使用恰好 i 跃点到达的所有节点。在邻居循环中，最终可以找到所有可以在 i + 1 跳中到达的节点。在这个循环中，相邻节点将被存储到一个队列中，用于下一次计数循环迭代。到达此类节点的可能路径数是到达其前任路径数的总和。一旦对当前计数循环迭代的每个节点完成此操作，队列和表就会被空实例交换/替换，算法可以重新开始。