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

I have been struggling with the following problem: I have a DFS outputted list: [0.2500000074505806, 0.6500000059604645, 0.15000000223517418, 0.45000000298023224, 0.45000000298023224, 0.8499999940395355, 0.15000000223517418] and want to transform this to a BFS ordering without first creating a tree and then applying BFS. For reference, this is a complete binary graph with depth 2.

Thanks in advance for the help.

CodePudding user response：

For general graphs, DFS doesn’t contain enough information to obtain the BFS output. But if you’re sure the graph is a complete binary tree on 7 nodes, and you ran DFS from the root and output is x1,x2,x3,…,x7, then the BFS output would be x1,x2,x5,x3,x4,x6,x7.

More generally, if you have the DFS output for a complete binary tree on n nodes, the permutation that gives the BFS output can be generated by the following algorithm:

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)

Output:

The algorithm takes as input the DFS sequence, and prints the root node, then does the following for each sublist in the FIFO queue: prints the left child, then adds about half of the elements as a sublist to a queue, then prints the right child, then adds about half of the elements as a sublist to a queue.

CodePudding user response：

When the tree is guaranteed to be a perfect binary tree, i.e. where the leaves of the tree are all on the bottom level, then you could use a pragmatic approach where you populate the levels of the level order traversal as separate lists, and then return the concatenation of those values:

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]

Example perfect tree:

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

Example run for that tree:

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