Graphs/Spanning Tree and Shortest Paths MCQ Quiz - Objective Question with Answer for Graphs/Spanning Tree and Shortest Paths - Download Free PDF
Last updated on Jun 12, 2025
Latest Graphs/Spanning Tree and Shortest Paths MCQ Objective Questions
Graphs/Spanning Tree and Shortest Paths Question 1:
The weight of minimum spanning tree in graph G, calculated using Kruskal’s algorithm is:
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 1 Detailed Solution
Concept:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Explanation:
Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}
For 5 vertices, we need 4 edges in MST,
So, edge set for MST = {2, 3, 4, 6}
Minimum spanning tree
Minimum cost 2 + 3 + 4 + 6 = 15
Graphs/Spanning Tree and Shortest Paths Question 2:
Which traversal algorithm is typically implemented using a stack data structure?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 2 Detailed Solution
The correct answer is DFS
Key Points
- Depth-First Search is typically implemented using a stack data structure. The algorithm explores as far as possible along each branch before backtracking. The stack helps in keeping track of the vertices to be visited, allowing the algorithm to backtrack efficiently.
- Breadth-First Search (BFS) is commonly implemented using a queue data structure.
Graphs/Spanning Tree and Shortest Paths Question 3:
Breath first traversal of a graph uses representation of graph in which data structure ?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 3 Detailed Solution
The correct answer is option 1: queue
Key Points
- Breadth First Traversal (BFS) is a graph traversal technique that visits all the vertices of a graph in breadthward motion, i.e., level by level.
- BFS uses a queue data structure to keep track of the vertices that need to be explored next.
- Once a node is visited, all of its adjacent unvisited vertices are added to the queue.
Additional Information
- Stack is used in Depth First Search (DFS), not BFS.
- List or doubly linked list may be used for adjacency representation but not directly for traversal control in BFS.
- Queue ensures FIFO order, which is essential for BFS to maintain level-order traversal.
Therefore, the correct answer is: option 1: queue
Graphs/Spanning Tree and Shortest Paths Question 4:
A complete graph of n nodes will have _______ number of spanning trees.
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 4 Detailed Solution
The correct answer is option 1: nn−2
Key Points
- The number of spanning trees in a **complete undirected graph** with n nodes is given by **Cayley’s formula**:
- This applies specifically to **complete graphs**, where every pair of distinct vertices is connected by a unique edge.
Examples:
- For n = 3 → spanning trees
- For n = 4 → spanning trees
Additional Information
- Option 2 (1): Only true for trees with exactly n − 1 edges, not for complete graphs.
- Option 3 (0): Invalid; a complete graph always has spanning trees if n ≥ 2.
- Option 4 (n/2): Not mathematically correct or relevant to spanning trees.
Hence, the correct answer is: option 1: nn−2
Graphs/Spanning Tree and Shortest Paths Question 5:
Dijkstra’s algorithm follows
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 5 Detailed Solution
The correct answer is Greedy algorithm.
Key Points
- Dijkstra's algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights.
- It finds the shortest path from the source node to all other nodes in the graph.
- Dijkstra's algorithm follows the Greedy algorithm paradigm, where it makes a series of choices, each of which looks best at the moment, to find the shortest path.
- It maintains a set of nodes whose shortest distance from the source is already known and repeatedly selects the node with the smallest known distance.
Additional Information
- Branch and bound is a general algorithm for finding optimal solutions of various optimization problems, particularly in discrete and combinatorial optimization. It is not specifically used in Dijkstra's algorithm.
- Backtracking is a general algorithm for finding solutions by trying partial solutions and then abandoning them if they are not suitable. It is used in problems like the N-Queens problem, but not in Dijkstra's algorithm.
- Dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is used in algorithms like the Floyd-Warshall algorithm, but Dijkstra's algorithm does not use this paradigm.
Top Graphs/Spanning Tree and Shortest Paths MCQ Objective Questions
Consider the following undirected graph with edge weights as shown:
The number of minimum-weight spanning trees of the graph is ______
Answer (Detailed Solution Below) 3
Graphs/Spanning Tree and Shortest Paths Question 6 Detailed Solution
Download Solution PDFAnswer:3 to 3
Concept:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Explanation:
The minimum weight in the graph is 0.1 choosing this we get.
Suppose we get two trees T1 and T2.
To connect to those two trees we got 3 possible edges of weight 0.9.
Hence we can choose any one of those 3 edges.
No of Minimum weight spanning tree is 3.
Depth First Search graph search algorithm uses _______ data structure for its implementation.
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 7 Detailed Solution
Download Solution PDF- Breadth-first search (BFS) and Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
- Depth First Search (DFS) uses Stack data structure. DFS uses backtracking technique. Remember backtracking can proceed by Stack.
- Breadth First Search (BFS) algorithm traverses a graph in a breadthwise manner and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
Queue structure is used in _______.
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 8 Detailed Solution
Download Solution PDF- Breadth-first search (BFS) and Depth First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.
- Breadth First Search (BFS) algorithm traverses a graph in a breadthwise manner and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.
- Depth First Search (DFS) uses Stack data structure. DFS uses backtracking technique. Remember backtracking can proceed by Stack.
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex t at a distance 4 from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _______.
Answer (Detailed Solution Below) 31
Graphs/Spanning Tree and Shortest Paths Question 9 Detailed Solution
Download Solution PDFAt a distance four from the root, tree will be like:
In this tree, maximum possible value of n at a distance 4 from the root is 31.
Alternate solution:
A tree with height h has maximum number of nodes = 2h+1 – 1
Here it is given that t is the nth vertex at a distance 4. We have to find the maximum value of n.
Here height = 4
Maximum value of n = 24+1 – 1 = 31
Which of the following algorithm solves the all-pair shortest path problem?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 10 Detailed Solution
Download Solution PDFPrim's algorithm: spanning Tree
Dijkstra's algorithm: single source shortest path
Bellman ford algorithm: single source shortest path
Floyd warshalls algorithm: all pair shortest path
The weight of minimum spanning tree in graph G, calculated using Kruskal’s algorithm is:
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 11 Detailed Solution
Download Solution PDFConcept:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Explanation:
Edge set for the given graph = {2, 3, 4, 5, 6, 7, 8}
For 5 vertices, we need 4 edges in MST,
So, edge set for MST = {2, 3, 4, 6}
Minimum spanning tree
Minimum cost 2 + 3 + 4 + 6 = 15
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:
I) Minimum Spanning Tree of G is always unique.
II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 12 Detailed Solution
Download Solution PDFConcept:
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
Example:
Graph G(V, E)
G(V, V – 1) → minimum spanning tree
If edge weights are distinct then there exist unique MST.
Hence Statement I is correct.
When edge weights are distinct and positive in that case shortest path between any two vertices of the graph is not always unique. Shortest path can be different even if the edge weights are unique.
Example:
Distance between A → C (3) and A → B → C (1 + 2 = 3), both paths has same distance.
Hence statement II is incorrect.
G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes eAnswer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 13 Detailed Solution
Download Solution PDFI. If e is the lightest edge of some cycle in G, then every MST of G includes e (INCORRECT)
Let G = (V, E) is a graph with 4 vertices and 5 edges.
Here, cycle contains the edge weights (3, 4, 5) but edge weight 3 is not included in the MST.
So, according to the cut-property of MST if is the lightest edge of some cycle in G, then every MST of G may or may not include e.
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e (CORRECT)
According to the cycle property of MST, same example as above. Here, cycle contains the edge weights (1, 2, 3) and 3 is the heaviest so edge weight 3 is excluded in the MST.
If there is heaviest edge in cycle, then we will exclude it from the MST because there are other low-cost edges are available to include in MST (because edge weights are distinct here).
Consider the directed graph given below.
Which one of the following is TRUE?
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 14 Detailed Solution
Download Solution PDFConcept:
This graph doesn’t have any cycle, hence there must exist a topological ordering.
R has an indegree from P and S. Q has indegree from P, R and S. Hence,
- P and S must appear R in the topological ordering.
- P, S, R must appear before Q in the topological ordering.
- Sequence of P and S has no indegree can be interchanged.
Therefore, the valid topological orders are PSRQ and SPRQ.
Explanation:
For topological ordering, the starting vertex must have 0 indegree. Hence, any one from P or S can be chosen.
If we choose P, then we need to choose the next vertex with indegree only from P. Hence, S is chosen.
After P and S, we choose a vertex with indegree only from P and S. Hence. R then Q.
Same could be performed with S instead of P.
The number of spanning trees for a complete graph with seven vertices is
Answer (Detailed Solution Below)
Graphs/Spanning Tree and Shortest Paths Question 15 Detailed Solution
Download Solution PDFConcept:
A spanning tree is a subset of Graph G, which has all the vertices covered with the minimum possible number of edges. Spanning tree doesn’t have cycles and it cannot be disconnected.
Formula:
Number of spanning trees possible with n nodes = nn-2
Calculation:
Here, the number of vertices is 7.
So, number of spanning trees possible = 77-2 = 75