Directed Graphs - Advanced MCQ Practice Sheet
Q1. In a directed graph, an edge going from node A to node B is called:
A. An undirected edge
B. A loop
C. A directed edge
D. A bidirectional edge
Answer: C
Explanation: A directed edge has a specific direction from one vertex to another.
Q2. What is the in-degree of a vertex?
A. Number of edges going out of the vertex
B. Number of edges coming into the vertex
C. Total number of connected vertices
D. None of the above
Answer: B
Explanation: In-degree is the number of edges coming into a vertex in a directed graph.
Q3. What is the out-degree of a vertex?
A. Number of vertices it is connected to
B. Number of loops
C. Number of edges going out from the vertex
D. Total number of incoming edges
Answer: C
Explanation: Out-degree is the count of outgoing edges from a vertex.
Q4. In a directed graph, the total number of edges is equal to:
A. Sum of in-degrees
B. Sum of out-degrees
C. Both A and B
D. None of the above
Answer: C
Explanation: Each edge contributes to one in-degree and one out-degree, so totals are equal.
Q5. Which data structure is most space-efficient for sparse graphs?
A. Adjacency matrix
B. Edge list
C. Adjacency list
D. Incidence matrix
Answer: C
Explanation: Adjacency lists only store existing edges, making them efficient for sparse graphs.
Q6. In a graph with n vertices, how many edges can a complete directed graph (no self-loops)
have?
A. n
B. n(n - 1)
C. n
D. n(n + 1)
Answer: B
Explanation: Each node can connect to (n - 1) others in a directed graph.
Q7. What is the maximum number of edges in a directed graph with 4 vertices (no self-loops)?
A. 6
B. 12
C. 16
D. 8
Answer: B
Explanation: Using formula n(n - 1): 43 = 12 edges.
Q8. Which representation of a graph allows quick edge existence check in O(1)?
A. Adjacency List
B. Adjacency Matrix
C. Edge List
D. Incidence List
Answer: B
Explanation: Adjacency matrix allows constant-time lookup of edge existence.
Q9. Which traversal explores all vertices reachable from a source node in a directed graph?
A. BFS
B. DFS
C. Both A and B
D. None
Answer: C
Explanation: Both BFS and DFS can be used to explore reachable vertices from a source.
Q10. A cycle in a directed graph is a path that:
A. Starts and ends at the same vertex
B. Has repeated edges
C. Contains undirected edges
D. Never returns to the starting node
Answer: A
Explanation: A cycle starts and ends at the same vertex with all edges directed.
Q11. Which algorithm is best for detecting cycles in a directed graph?
A. BFS
B. DFS with recursion stack
C. Prims Algorithm
D. Dijkstras Algorithm
Answer: B
Explanation: DFS with a recursion stack helps track visited and backtracked nodes to detect
cycles.
Q12. Topological sorting is only possible for:
A. Undirected graphs
B. Directed Acyclic Graphs (DAGs)
C. Cyclic graphs
D. Weighted graphs
Answer: B
Explanation: Topological sort requires no cycles; it works only on DAGs.
Q13. Which one of the following is true for a DAG?
A. It contains no cycles
B. It must be connected
C. Every vertex has equal in-degree and out-degree
D. It has only one root
Answer: A
Explanation: By definition, DAGs (Directed Acyclic Graphs) do not contain cycles.
Q14. In an adjacency list for a directed graph, the edges are:
A. Stored once for each vertex pair
B. Stored in both directions
C. Stored from source to destination only
D. Ignored
Answer: C
Explanation: Edges in directed graphs are stored in the direction from source to destination.
Q15. What is the best way to represent a dense directed graph for fast edge lookup and update?
A. Adjacency matrix
B. Adjacency list
C. Incidence list
D. Queue
Answer: A
Explanation: For dense graphs, adjacency matrices provide fast lookup and constant-time
updates.
