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.
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:
1
2
5
3
4
6
7
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.