Testbook Test Series: Algorithms - Graph Algorithms

Question

Consider the following statements:

$A.$ In a weighted undirected graph $G = (V, E, w)$, breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in $O(V + E)$ time.

$B.$ In a weighted undirected tree $G = (V, E, w)$, breadth-first search from a vertex s finds single-source shortest paths from s (via parent pointers) in $O(V + E)$ time.

$C.$ If a graph represents tasks and their inter-dependencies (i.e., an edge $(u, v)$ indicates that $u$ must happen before $v$ happens), then the breadth-first search order of vertices is a valid order in which to tackle the tasks.

Which of the above is TRUE?

Comments

According to C) there is an interdependency

what that interdependency means? Is it not represent directed graph?

---

Here we have to create a graph in which 'tasks' are vertices and lets say there are two task T₁ and T₂ .Now interdependency means if T₁ IS DONE before T₂ then directed edge is from T₁ to T₂ , else if T₂ is done before T₁ then there is a directedd edge from T₂ to T₁ , else no edge . In the end we will get a directed graph in which (T₁,T₂) is a edge only when  T₁ is done before T₂ , lets say this as T₁ is adjacent to T₂ if there is an edge (T₁,T₂) .

Now if you give this directed but unweighted graph and a source 'T_n' as input to BFS algorithm it will generate a BFS tree .Now in this Tree start with source 'T_n' then children of T_n in any order then their children in any order  and so on . If you do like this, all tasks which are on the same level are done one parallely then you will get a valid order in which to tackle tasks.

 

---

A. Statement is true only in case of unweighted graphs.

B In a tree, there is only one path between two vertices, and breadth-first search finds it.

C.  We’d prefer depth-first search, which can easily be used to produce a topological sort of the graph, which would correspond to a valid task order. BFS can produce incorrect results.

Did't understood the C part. Anyone?