有几个BFS订单？

Question

给定一个图G(V，E)和一个源顶点s，有多少个BFS命令，一个算法是如何找到它们的？

示例

只有一个顶点A的图对s=A有一个BFS排序，即A。

具有两个连通点A和B的图对于s=A有一个BFS序，即A，B

一个树点A、B和C都相互连接的图对s=A有两个BFS序，即A、B、C和A、C、B。

Answer 1

您需要一个BFS算法，以回溯和查找所有有效的订单。您将需要在pass中进行搜索，每层一次(从开始节点的最短距离)。

"done" <- [start node]
"open" <- [all other nodes]
"pending" <- empty list

while "open" is not empty
    for each node in "done",
        for each adjacent node
            if the node is not in "done",
                add it to "pending".
    for each node in "pending"
        add node to "done", recording the added step in a solution
        recur, using new path as set of start nodes, other nodes as "pending"
            BUT ... if no nodes are pending, record this path as a solution.

这足够让你动弹了吗？

请注意，您可以通过动态编程大大缩短这一点:为给定的path集和最新节点编写子解决方案。对于大型图，这允许您避免重复来自ABCD和ACBD的延续。这两起案件将继续审理同一案件。

Answer 2

我认为，如果我们画一个bfs树，我们可以得到假设级别从0到n，N(级别no)给出了该级别上的节点数，然后(i=0；i)

Answer 3

对于有限图，计数BFS序等价于计数DFS前后序，后者等价于计数拓扑排序。这是在夏普#P完全复杂性类，并被认为是一个比NP更难的问题。