PRACTICE • LEARN • GROW
Graphs MCQs
Solve topic-wise placement questions and improve your skills.
Graphs Progress
0 of 39 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
What is the time complexity of Breadth-First Search (BFS) on a graph with V vertices and E edges represented as an Adjacency List?
A.
O(V + E)
B.
O(V^2)
C.
O(V * E)
D.
O(E log V)
Explanation & Key
Correct Answer:
2
Which algorithm is used to find the shortest path from a single source in a weighted graph with NON-NEGATIVE edge weights?
A.
Floyd-Warshall Algorithm
B.
Dijkstra's Algorithm
C.
Kruskal's Algorithm
D.
Kosaraju's Algorithm
Explanation & Key
Correct Answer:
3
What is the time complexity of Dijkstra's algorithm implemented with a Min-Priority Queue (Binary Heap)?
A.
O(V^2)
B.
O(V * E)
C.
O((V + E) log V)
D.
O(E^2)
Explanation & Key
Correct Answer:
4
Which algorithm finds single-source shortest paths in graphs with negative edge weights and detects negative weight cycles?
A.
Dijkstra's Algorithm
B.
Prim's Algorithm
C.
Kruskal's Algorithm
D.
Bellman-Ford Algorithm
Explanation & Key
Correct Answer:
5
What is the time complexity of the Bellman-Ford algorithm?
A.
O(V * E)
B.
O(V + E)
C.
O(V^3)
D.
O(E log V)
Explanation & Key
Correct Answer:
6
What is the time complexity of the Floyd-Warshall all-pairs shortest path algorithm?
A.
O(V * E)
B.
O(V^3)
C.
O(V^2 log V)
D.
O(V + E)
Explanation & Key
Correct Answer:
7
Topological Sorting is possible ONLY on which class of graphs?
A.
Undirected Connected Graphs
B.
Graphs with directed cycles
C.
Directed Acyclic Graphs (DAG)
D.
Complete Bipartite Graphs
Explanation & Key
Correct Answer:
8
Kahn's algorithm for Topological Sorting uses which metric of graph vertices?
A.
Out-degree of vertices using a Stack
B.
Eccentricity of vertices
C.
Betweenness centrality
D.
In-degree of vertices using a Queue
Explanation & Key
Correct Answer:
9
Which algorithm finds a Minimum Spanning Tree (MST) by sorting edges and adding non-cycle edges using Disjoint Set Union (DSU)?
A.
Kruskal's Algorithm
B.
Prim's Algorithm
C.
Dijkstra's Algorithm
D.
Tarjan's Algorithm
Explanation & Key
Correct Answer:
10
What is the time complexity of Kruskal's Algorithm on a graph with V vertices and E edges?
A.
O(V^2)
B.
O(E log E) or O(E log V)
C.
O(V * E)
D.
O(V + E)
Explanation & Key
Correct Answer:
11
How does Prim's algorithm differ fundamentally from Kruskal's algorithm for finding an MST?
A.
Prim's algorithm works on directed graphs whereas Kruskal's does not
B.
Prim's uses dynamic programming whereas Kruskal's uses backtracking
C.
Prim's grows a single tree vertex by vertex; Kruskal's grows a forest by adding edges across components
D.
Kruskal's produces an arborescence whereas Prim's produces a DAG
Explanation & Key
Correct Answer:
12
What is a Bipartite Graph and how can it be tested using BFS/DFS?
A.
A graph with exactly two vertices
B.
A directed graph with two disjoint cycles
C.
A graph where every vertex has degree 2
D.
A graph whose vertices can be 2-colored such that no two adjacent vertices share the same color; verified if graph contains no odd-length cycles
Explanation & Key
Correct Answer:
13
What is a Bridge (Cut-Edge) in a connected graph?
A.
An edge whose removal increases the number of connected components
B.
An edge with the maximum weight in an MST
C.
An edge that connects two leaf nodes
D.
A self-loop edge
Explanation & Key
Correct Answer:
14
Which algorithm detects Bridges and Articulation Points in a graph in a single DFS pass of O(V + E) time?
A.
Floyd-Warshall Algorithm
B.
Tarjan's Bridge-Finding Algorithm using discovery and low-link times
C.
Kruskal's Algorithm
D.
Bellman-Ford Algorithm
Explanation & Key
Correct Answer:
15
What are the two passes performed in Kosaraju's algorithm to find Strongly Connected Components (SCCs)?
A.
1) BFS to find shortest paths; 2) Dijkstra on remaining nodes
B.
1) Kahn topological sort; 2) Kruskal MST pass
C.
1) DFS on original graph to fill stack by finishing times; 2) DFS on transposed (reversed) graph in stack order
D.
1) Prim algorithm; 2) Floyd-Warshall pass
Explanation & Key
Correct Answer:
16
How many edges does a Minimum Spanning Tree of a connected undirected graph with V vertices contain?
A.
V
B.
V * (V - 1) / 2
C.
2 * V - 1
D.
V - 1
Explanation & Key
Correct Answer:
17
What does the Handshaking Lemma state for any undirected graph?
A.
The sum of the degrees of all vertices equals twice the number of edges (2 * E)
B.
The number of vertices with odd degree is always odd
C.
Every vertex must have at least one edge
D.
The number of edges equals V^2
Explanation & Key
Correct Answer:
18
What is the maximum number of edges in a simple undirected graph with V vertices?
A.
V^2
B.
V * (V - 1) / 2
C.
2^V
D.
V * (V + 1) / 2
Explanation & Key
Correct Answer:
19
What is an Eulerian Path in a connected graph?
A.
A path that visits every VERTEX exactly once
B.
The shortest path between source and destination
C.
A trail in a finite graph that visits every EDGE exactly once
D.
A cycle that contains all vertices
Explanation & Key
Correct Answer:
20
What is a Hamiltonian Path in a graph?
A.
A path that visits each edge exactly once
B.
A spanning tree with minimum weight
C.
A cycle containing only negative edge weights
D.
A path in an undirected or directed graph that visits each VERTEX exactly once
Explanation & Key
Correct Answer:
21
How does cycle detection in an UNDIRECTED graph differ from a DIRECTED graph during DFS?
A.
Undirected checks for a visited neighbor that is NOT parent; Directed requires tracking recursion call stack (back-edge)
B.
Undirected graphs cannot contain cycles
C.
Directed graphs can only detect cycles using BFS
D.
They use the exact same parent check
Explanation & Key
Correct Answer:
22
What is the space complexity of storing a graph with V vertices and E edges using an Adjacency Matrix?
A.
Theta(V + E)
B.
Theta(V^2)
C.
Theta(E^2)
D.
Theta(V * E)
Explanation & Key
Correct Answer:
23
What is the Ford-Fulkerson method used for?
A.
Finding Strongly Connected Components
B.
Finding all-pairs shortest paths
C.
Computing the Maximum Flow in a flow network
D.
Solving the Travelling Salesperson Problem
Explanation & Key
Correct Answer:
24
What does the Max-Flow Min-Cut Theorem state?
A.
The flow is bounded by the number of edges
B.
Minimum cut capacity is always zero in connected graphs
C.
Maximum flow is equal to the shortest path distance
D.
The maximum amount of flow from source to sink equals the total capacity of the minimum cut separating source from sink
Explanation & Key
Correct Answer:
25
In the A* Search algorithm, what does the evaluation function `f(n) = g(n) + h(n)` represent?
A.
`g(n)` is exact cost from start to n; `h(n)` is heuristic estimated cost from n to goal
B.
`g(n)` is heuristic and `h(n)` is edge weight
C.
`g(n)` is tree depth and `h(n)` is vertex degree
D.
`f(n)` is the Euclidean distance squared
Explanation & Key
Correct Answer:
26
What makes a heuristic function `h(n)` admissible in A* search?
A.
It returns integer values only
B.
It never overestimates the true cost to reach the goal
C.
It is strictly greater than the actual cost
D.
It calculates Manhattan distance exclusively
Explanation & Key
Correct Answer:
27
What is the diameter of a tree graph and how can it be found using BFS?
A.
Count total edges and divide by 2
B.
Compute maximum degree vertex
C.
Run BFS from an arbitrary node to find farthest node u; run second BFS from u to find farthest node v; distance(u, v) is diameter
D.
Run Floyd-Warshall on all nodes
Explanation & Key
Correct Answer:
28
What is a Biconnected Component in an undirected graph?
A.
A subgraph with two vertices
B.
A graph where every vertex has degree 2
C.
A bipartite graph with equal partition sizes
D.
A maximal connected subgraph that remains connected after removing any single vertex (has no articulation points)
Explanation & Key
Correct Answer:
29
In 0-1 BFS (a graph where edge weights are either 0 or 1), which data structure finds shortest paths in O(V + E) time?
A.
Deque (push to front if weight 0, push to back if weight 1)
B.
Priority Queue (Binary Heap)
C.
Stack
D.
Disjoint Set Union
Explanation & Key
Correct Answer:
30
What is the time complexity of cycle detection in an undirected graph with V vertices using Disjoint Set Union (Union-Find)?
A.
O(V^3)
B.
O(E * alpha(V)) where alpha is the Inverse Ackermann function
C.
O(E log E)
D.
O(V * E)
Explanation & Key
Correct Answer:
31
What is the time complexity of Breadth-First Search (BFS) on a graph represented using an Adjacency List?
A.
O(V + E)
B.
O(V^2)
C.
O(V * E)
D.
O(log V)
Explanation & Key
Correct Answer:
32
How is cycle detection implemented in a DIRECTED graph using Depth-First Search (DFS)?
A.
Using 3-coloring: track nodes currently on the active recursion call stack (Gray/in-stack); a back-edge to an in-stack node confirms a cycle
B.
Check if edge count E >= V
C.
A simple visited boolean array is sufficient
D.
Using BFS queue size
Explanation & Key
Correct Answer:
33
What is the Bellman-Ford algorithm used for, and what is its time complexity?
A.
Single-source shortest path that handles negative edge weights and detects negative weight cycles, running in O(V * E)
B.
All-pairs shortest path in O(V^3)
C.
Minimum Spanning Tree in O(E log V)
D.
Topological sort in O(V + E)
Explanation & Key
Correct Answer:
34
What is the Floyd-Warshall algorithm used for and what is its time complexity?
A.
All-Pairs Shortest Path running in O(V^3) time using 3 nested loops
B.
Single-source shortest path in O(V + E)
C.
Bipartite graph matching in O(V^2)
D.
Topological sorting in O(V log V)
Explanation & Key
Correct Answer:
35
What is a Bipartite Graph, and how can you check if a graph is bipartite in O(V + E) time?
A.
A graph whose vertices can be partitioned into two sets such that no two adjacent vertices share the same set; verified using 2-coloring via BFS/DFS
B.
A graph with exactly two edges
C.
A directed graph with no cycles
D.
A graph where every node has degree 2
Explanation & Key
Correct Answer:
36
In Tarjan's Strongly Connected Components (SCC) algorithm, what do `disc[u]` and `low[u]` represent?
A.
`disc[u]` is discovery timestamp; `low[u]` is the lowest discovery time reachable from u via its subtree and back-edges
B.
In-degree and out-degree of vertex u
C.
Shortest distance and predecessor of vertex u
D.
Subtree size and height
Explanation & Key
Correct Answer:
37
What is the condition that guarantees a connected undirected graph has an Eulerian Circuit (a cycle visiting every edge exactly once)?
A.
Every vertex in the graph must have an EVEN degree
B.
All vertices must have odd degree
C.
The graph must be a tree
D.
The graph must have no cycles
Explanation & Key
Correct Answer:
38
In the Disjoint Set Union (DSU) data structure, what time complexity does Path Compression + Union by Rank achieve per operation?
A.
Nearly O(1) amortized, specifically O(alpha(n)) where alpha is the Inverse Ackermann function
B.
Strictly O(log n)
C.
O(n)
D.
O(n log n)
Explanation & Key
Correct Answer:
39
In 0-1 BFS (finding shortest path where edge weights are only 0 or 1), which data structure replaces the Priority Queue to achieve O(V + E) time?
A.
Double-Ended Queue (Deque): push 0-weight edges to FRONT and 1-weight edges to BACK
B.
Two separate stacks
C.
Min-Heap
D.
Circular array of size 2
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
