how to construct tree from BFS

[waxen hornet]

Why are the lines dotted from D to C and F to E

[novel anvil]

not quite sure what do you mean by BFS tree, I’m assuming its similar to DFS tree

usually in such “graph traversal trees” you have two types of situations

let v be the current vertex you’re on and let u be the vertex you’re trying to move to

if you HAVE NOT visited vertex u, you can mark it as visited, add it into queue and create undotted line

if you HAVE visited it though, you have a “back edge” and you essentially can mark it as a dotted line

now, undotted line is a tree edge. you can assume that because tree edge is only created if we have a situation of one visited vertex and one unvisited vertex (together can happen at most n - 1 times, where n is the amount of vertices in a graph)

and a dotted line is a “back edge”, which makes it a graph essentially

now lets start a traversal from A

on first iteration we get A->E, A->D and A->C, which are all undotted

in second iteration we get D->C dotted, C->F and E->B undotted and then E->F dotted (we processed C before E)

lastly, we get the B->F edge which is obviously dotted, cause both vertices have alr been visited