Data Structure Questions and Answers – Directed Acyclic Graph

Uncategorized

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Directed Acyclic Graph”.

1. What would be the output of the following C++ program if the given input is

0 0 0 1 1
0 0 0 0 1
0 0 0 1 0
1 0 1 0 0
1 1 0 0 0
 
#include <bits/stdc++.h>
using namespace std;
bool visited[5];
int G[5][5];
 
void fun(int i)
{
	cout<<i<<" ";
	visited[i]=true;
	for(int j=0;j<5;j++)
		if(!visited[j]&&G[i][j]==1)
			fun(j);
}
 
int main()
{   
	for(int i=0;i<5;i++)
		for(int j=0;j<5;j++)
			cin>>G[i][j];
 
	for(int i=0;i<5;i++)
		visited[i]=0;
 
	fun(0);
		return 0;
}

A) 0 2 3 1 4
B) 0 3 2 4 1
C) 0 2 3 4 1
D) 0 3 2 1 4

Explanation: The adjacency matrix of a graph G is given as input, and the function ‘fun’ prints the DFS traversal.

2. Which of the given statement is true?
A) All the Cyclic Directed Graphs have topological sortings
B) All the Acyclic Directed Graphs have topological sortings
C) All Directed Graphs have topological sortings
D) All the cyclic directed graphs hace non topological sortings

Explanation: Topologically, Cyclic Directed Graphs cannot be sorted.

3. For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?
A) True
B) False
Explanation: If there are such vertices, the graph has a cycle, which contradicts the first part of the assertion.

4. What is the value of the sum of the minimum in-degree and maximum out-degree of an Directed Acyclic Graph?
A) Depends on a Graph
B) Will always be zero
C) Will always be greater than zero
D) May be zero or greater than zero

Explanation: There is a source and a sink vertex in any Directed Acyclic Graph.

5. Every Directed Acyclic Graph has at least one sink vertex.
A) True
B) False

Explanation: A sink vertex is defined as a vertex with a zero outgoing degree.

6. Which of the following is not a topological sorting of the given graph?

data-structure-questions-answers-directed-acyclic-graph-q2


A) A B C D E F
B) A B F E D C
C) A B E C F D
D) A B C D F E

Explanation: Topological sorting is a linear arrangement of vertices in which u falls before v in the ordering for any directed edge uv from vertex u to vertex v. In the order A B C D F E, F comes before E.

7. 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

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.

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

Explanation: Topological sorting takes O(V+E) time, where V and E are the number of vertices and edges, respectively.

9. 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
Explanation: A Hamiltonian path can only exist if all of the vertices are connected by a path; otherwise, there would be no unique topological form.

10. What sequence would the BFS traversal of the given graph yield?

data-structure-questions-answers-directed-acyclic-graph-q6

A) A F D B C E
B) C B A F E D
C) A B D C E F
D) E F D C B A

Explanation: Until going on to the next step in BFS, nodes are examined first, followed by the neighbours of the current node.

A directed acyclic graph (DAG or dag /d/ (About this soundlisten)) is a graph that does not have any directed cycles. That is, it is made up of vertices and edges (also known as arcs), each of which is directed from one vertex to the next in such a way that following those directions can never result in a closed loop. A directed graph is a DAG if and only if the vertices can be topologically ordered in a linear order that is consistent across all edge directions. From biology (evolution, family trees, epidemiology) to sociology (citation networks) to computing, DAGs have a wide range of scientific and computational applications (scheduling).

Leave a Reply

Your email address will not be published. Required fields are marked *