CODEWITHSUNDEEP
data-structuresgraphtreedepth-first-searchbreadth-first-search
Anshul Sharma
Anshul Sharma

Reputation: 27

BFS tree to graph

Suppose we obtain the following BFS tree rooted at node D for an undirected graph with vertices {A,B,C,D,E,F,G,H}. Tree How to determine whether a particular edge is present or not in the original graph?

This is a multiple choice type question:

Which of the following edges is not present in the original graph?

  1. (F, G)
  2. (B, E)
  3. (A, G)
  4. (E, H)

Upvotes: 1

Views: 4352

Answers (3)

h1m4n3hu
h1m4n3hu

Reputation: 1

Difference between the level of nodes should be no more than 1, so as to create a BFS tree as its just a matter of levels.

B is just one level away from E. Same goes with E and H. A and G are in the same level so the difference is 0.

F and G are 2 levels apart, so they might not be present in the Graph-if the edge between them was present then the BFS tree might not have taken pains to traverse other nodes, that currently are there in level 3(C, B and H), before F.

Upvotes: 0

VFX
VFX

Reputation: 496

The edges in the BFS tree are a subset of the edges in the original graph and multiple original graphs might give the same BFS tree, so the answer to your question is:

  • If the BFS tree has an edge => the original graph has this edge too.
  • If the BFS tree does not have an edge => the original graph might or might not have this edge.

    so it is not always possible to know whether the original graph has the edge or not.

Answering the MCQ question after adding it to the original question:
The way BFS works is level by level, that means all the nodes in level(i) will be processed before any node in level(i+1) is processed.
So all the nodes in L3 should be add to the queue before any node in L4 is added to the queue, so if (F,G) exits in the original graph then the node F should show in L3 as a child of node G instead of L4... so the answer is the edge (F,G).

Upvotes: 0

trincot
trincot

Reputation: 350202

You cannot know exactly which edges are in the graph, but you can be sure of some that are (namely those in the BST) and of some that are not (as otherwise the BST would have looked differently):

  1. Every edge in the BST is also an edge in the graph
  2. Every edge, that would allow a path from the root to a certain node that is shorter than the shortest path between those two nodes in the BST, is not a member of the graph.

Let's look at the following edges:

  1. (F,G)

If that edge would be in the graph, then the shortest path from D to F would be D-G-F, having length 2, but in the BST the path from D to F has length 3. This is inconsistent, as a BST always finds the shortest path between the root and any other node in the graph.

  1. (B,E)

This would allow a path from D to E of length 3, which is consistent with the BST. So this could be an edge in the graph, but doesn't have to.

  1. (A,G)

This would allow a path from D to A or from D to G of length 2, which is consistent with the BST, as the BST offers shorter paths in both cases. So this could be an edge in the graph, but doesn't have to.

  1. (E,H)

This would allow a path from D to E of length 3, which is consistent with the BST. So this could be an edge in the graph, but doesn't have to.

Of these four edges, only (F,G) is a clear case: that edge cannot be in the graph.

Upvotes: 1

Related Questions