Data Structure Questions and Answers – Directed Graph

Uncategorized

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

1. Assuming value of every weight to be greater than 10, in which of the following cases the shortest path of a directed weighted graph from 2 vertices u and v will never change?
A) add all values by 10
B) subtract 10 from all the values
C) multiply all values by 10
D) in both the cases of multiplying and adding by 10

Explanation: The shortest path can change in addition or subtraction because the number of edges between different paths can vary, while the path will not change in multiplication.

2. What is the maximum possible number of edges in a directed graph with no self loops having 8 vertices?
A) 28
B) 64
C) 256
D) 56

Explanation: Any vertex in a graph with V vertices can be connected to a maximum of V-1 vertices.

3. What would be the DFS traversal of the given Graph?

data-structure-questions-answers-directed-graph-q8

A) ABCED
B) AEDCB
C) EDCBA
D) ADECB

Explanation: In this case, two options exist, one of which is ADEBC.

4. What would be the value of the distance matrix, after the execution of the given code?

#include <bits/stdc++.h>
#define INF 1000000
int graph[V][V] = {   {0,   7,  INF, 4},
                      {INF, 0,   13, INF},
                      {INF, INF, 0,   12},
                      {INF, INF, INF, 0}
                  };
 
int distance[V][V], i, j, k;
 
for (i = 0; i < V; i++)
        for (j = 0; j < V; j++)
    	distance[i][j] = graph[i][j];
 
for (k = 0; k < V; k++)
	for (i = 0; i < V; i++)
        	for (j = 0; j < V; j++)
                {
            		if (distance[i][k] + distance[k][j] < distance[i][j])
                		distance[i][j] = distance[i][k] + distance[k][j];
 
                           return 0;
                }

A)

{            
    {0,   7,  INF, 4},
    {INF, 0,   13, INF},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

B)

{            
    {0,   7,  20, 24},
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
};

C)

{ 
    {0,   INF,  20, 24},
    {INF, INF,   13, 25},
    {INF, INF, 0,   12},
    {INF, INF, INF, 0}
    {INF, 0,   13, 25},
    {INF, INF, 0,   12},
    {24, INF, INF, 0}
};

D) None of the mentioned

Explanation: The shortest sub distances are calculated by the software.

5. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no cycles in the graph?
A) 21
B) 7
C) 6
D) 49

Explanation: The difference between the number of vertices and edges is 1 if no cycles occur.

6. Dijkstra’s Algorithm will work for both negative and positive weights?
A) True
B) False

Explanation: All weights in Dijkstra’s Algorithm are assumed to be non-negative.

7. A graph having an edge from each vertex to every other vertex is called a ___________
A) Tightly Connected
B) Strongly Connected
C) Weakly Connected
D) Loosely Connected

Explanation: This is a part of the nomenclature scheme for graph theory.

8. What is the number of unlabeled simple directed graph that can be made with 1 or 2 vertices?
A) 2
B) 4
C) 5
D) 9

Explanation:

data-structure-questions-answers-directed-graph-q3

9. Floyd Warshall Algorithm used to solve the shortest path problem has a time complexity of __________
A) O(V*V)
B) O(V*V*V)
C) O(E*V)
D) O(E*E)

Explanation: The algorithm employs Dynamic Programming to examine all possible paths.

10. All Graphs have unique representation on paper.
A) True
B) False

Explanation: On paper, the same graph can be drawn in a variety of ways.

A directed graph (or digraph) is a graph with a set of vertices connected by directed edges, commonly referred to as arcs. A directed graph may have loops (that is, arcs that directly link nodes to themselves) according to the aforementioned description, but some authors prefer a stricter definition that excludes loops from directed graphs. Driven graphs with loops are referred to as loop-digraphs, whereas directed graphs without loops are referred to as plain directed graphs (see section Types of directed graphs).

Leave a Reply

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