有没有办法从 DFS 输出到 BFS 输出？

Question

我一直在努力解决以下问题：我有一个 DFS 输出列表： [0.2500000074505806, 0.6500000059604645, 0.15000000223517418, 0.45000000298023224, 0.45000000298023224, 0.8499999940395355, 0.15000000223517418] 并希望在不先创建树然后应用 BFS 的情况下将其转换为 BFS 排序。作为参考，这是一个深度为 2 的完整二进制图。

在此先感谢您的帮助。

Answer 1

对于一般图，DFS 不包含足够的信息来获得 BFS 输出。但是，如果您确定该图是 7 个节点上的完全二叉树，并且您从根开始运行 DFS 并且输出是 x1,x2,x3,…,x7，那么 BFS 输出将是 x1,x2 ,x5,x3,x4,x6,x7.

更一般地说，如果您有 n 个节点上的完整二叉树的 DFS 输出，则可以通过以下算法生成给出 BFS 输出的排列：

k = 3   # number of levels in complete binary tree
n = 2**k   #so node labels are 1,2,...,n-1
L = list(range(1, n))

def toBFS(L):
    #input: a sequence of node labels, obtained by DFS on a complete binary tree
    #output: the sequence of node labels if BFS was performed
    #Q = a queue of all sublists to be processed
    #each sublist q has length 2^k-2
    #process each sublist by printing 1st, and n/2th element
    #and partitioning into two subsublists, both added to queue
    print(L[0])
    Q = []
    Q.append(L[1:len(L)])
    while len(Q) > 0:
        q = Q.pop(0)    #removes first element of Q
        if len(q) <= 2:
            for x in q:
                print(x)
        else:
            print(q[0])
            n = len(q)
            print(q[n//2])
            Q.append(q[1:n//2])
            Q.append(q[n//2+1:n])
        
toBFS(L)

输出：

该算法将 DFS 序列作为输入，并打印根节点，然后对 FIFO 队列中的每个子列表执行以下操作：打印左侧 child，然后添加大约一半的元素作为子列表到队列，然后打印右边的 child，然后将大约一半的元素作为子列表添加到队列。

Answer 2

当树保证是 perfect binary tree 时，即树的叶子都在底层，那么您可以使用实用的方法来填充层次顺序遍历的层次作为单独的列表，然后 return 这些值的串联：

def preorder_to_levelorder(seq):
    height = int(len(seq) ** 0.5)
    levels = [[] for _ in range(height+1)]
    it = iter(seq)
    
    def recur(depth):
        if depth > height:
            return
        try:
            val = next(it)
        except:
            return
        levels[depth].append(val)
        recur(depth + 1)
        recur(depth + 1)

    recur(0)
    return [val for level in levels for val in level]

完美树示例：

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

该树的示例运行：

preorder = [4, 2, 1, 3, 6, 5, 7]
print(preorder_to_levelorder(preorder))  # [4, 2, 6, 1, 3, 5, 7]

有没有办法从 DFS 输出到 BFS 输出？

Is there a way to get from a DFS output to a BFS output?

python

graph

list

breadth-first-search

depth-first-search