Test by Bikram | Mock GATE | Test 2 | Question: 29

Question

Given a graph $G$ with vertex set $V$ and edge set $E$, which of the following statements is/are correct about graph $G$?

1. If $G$ is directed and acyclic, the asymptotic algorithmic complexity of topological sort on $G$ is $O$$\left ( \left [ V \right ] +\left [ E \right ]\right )$, assuming edges are represented in adjacency lists rather than an adjacency matrix.
2. If $G$ is directed or undirected, the asymptotic algorithmic complexity of breadth-first search on $G$ is $O$$\left ( \left [ V \right ] +\left [ E \right ]\right )$, assuming edges are represented in adjacency lists rather than an adjacency matrix.
3. If $G$ is undirected, during a depth-first search of $G$, exactly four types of edges might be identified: tree edges (members of the spanning forest), back edges (linking descendants to ancestors), forward edges (non-tree edges linking ancestors to descendants), and cross edges (all other remaining links).

• A. I only
• B. III only
• C. I and II only
• D. I, II and III

Comments

so in directed acyclic graph only back edges is not possible. but all other 3 types of edges are possible?

---

@sheshang

yes, in Directed acyclic graph only 3 types of edges are possible like Tree edge, Forward edge and Cross edge.

For Undirected acyclic graph only Tree edge is possible. 

---

• If graph is undirected, DFS produces a tree that can only have tree edges or back edges.
   
• If graph is directed, DFS produces a tree that can have four types of edges — tree, back, cross and forward.
   
• A directed graph is a DAG iff its DFS doesn't have back edges.

---

Source: CLRS page 609.

---

Answer 1

Option I  True

Reason :

The topological sort algorithm uses a depth-first search. As nodes are finished, they are added to the front of a linked list. Since no node can be finished after its ancestors are, nodes will appear later in the final list than their ancestors.

(Ancestors, meaning sources of incoming edges on a node x, are like “dependencies” of x.) Since depth-first search
runs in O(|V | + |E|), so  topological sort also takes O(|V|  + |E| ) .

Option II  True 

Reason:

Both BFS and DFS  maintain a collection of nodes waiting to be visited; while the collection is non-empty, these algorithms pull another node out of the collection and put the node’s children into the collection.

 The collection is a Stack, while for depth-first search, For a breadth-first search, the collection is a Queue .

Since each node is touched twice (once on entering the collection and once when it is visited), and each edge is touched once, the algorithms run in O(|V | + |E|) asymptotic algorithmic complexity.

Option III False 

Reason: " If G is undirected, during a depth-first search of G, exactly four types of edges might be identified " - This line is wrong.

G is UNDIRECTED GRAPH. When we do a depth-first search of a directed graph, four edge types could be possible. 

On an undirected graph, edges can be traversed in both direction, so only tree edges and back edges can be possible in undirected graphs . 

Comments

"The collection is a queue, while for depth-first search, For a breadth-first search, the collection is a stack."

I think above line has error because collection is stack for dfs and queue for bfs. So, please have a look once.

---

Thank you Neeraj :) corrected .

---

Sir, why Undirected graphs cannot have Forward edges ?

I found this :

https://stackoverflow.com/questions/19886504/forward-edge-in-an-undirected-graph

But, still it is not very clear to me :(