# Data Structure Questions and Answers-Directed Acyclic Graph

## Click on any option to know the CORRECT ANSWERS

 Question 1
Every Directed Acyclic Graph has at least one sink vertex.
 A True B False

Question 1 Explanation:
A sink vertex is a vertex which has an outgoing degree of zero.

 Question 2
Which of the following is a topological sorting of the given graph?
 A A B C D E F B A B F E D C C A B E C F D D All of the Mentioned

Question 2 Explanation:
Topological sorting is a linear arrangement of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

 Question 3
With V(greater than 1) vertices, how many edges at most can a Directed Acyclic Graph possess?
 A (V*(V-1))/2 B (V*(V+1))/2 C (V+1)C2 D (V-1)C2

Question 3 Explanation:
The first edge would have an outgoing degree of atmost V-1, the next edge would have V-2 and so on, hence V-1 + V-2.... +1 equals (V*(V-1))/2.

 Question 4
The topological sorting of any DAG can be done in ..... time.
 A cubic B quadratic C linear D logarithmic

Question 4 Explanation:
Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.

 Question 5
If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
 A Many Hamiltonian paths are possible B No Hamiltonian path is possible C Exactly 1 Hamiltonian path is possible D Given information is insufficient to comment anything