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?**

**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 ConnectedC) 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:

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