HomeSubjectsUniversityBlogAbout

Graph Algorithms

Topic in Data Structures & Algorithms

210 total MCQsShowing 30 with explanations10 Easy10 Medium10 Hard
Start Timed Quiz on Graph AlgorithmsBack to Data Structures & Algorithms

About This Topic

Graph algorithms solve problems on vertices connected by edges, such as exploring reachability, finding shortest paths and building minimum spanning trees. Traversal MCQs compare breadth-first search, which uses a queue, with depth-first search, which uses a stack or recursion, both running in O(V + E). Shortest-path items cover Dijkstra's algorithm and its failure with negative edges, Bellman-Ford for negative weights, and Floyd-Warshall for all pairs. For spanning trees you should contrast Prim's vertex-growing approach with Kruskal's edge-sorting method using union-find to detect cycles. Topological sorting on directed acyclic graphs, cycle detection and Tarjan's strongly connected components complete the set.

Below are 30 practice questions from a pool of 210 Graph Algorithms MCQs, one of 12 topics in Data Structures & Algorithms. Each shows the correct answer with an explanation; when you are ready, take a timed quiz to test recall under exam conditions.

Practice Questions

Each question below shows the correct answer with a full explanation. Use these to build conceptual understanding before attempting a timed quiz.

Graph AlgorithmsEasy

Q1. What is the time complexity of DFS on a graph with V vertices and E edges?

  1. A.O(V + E)✓ Correct
  2. B.O(V × E)
  3. C.O(E^2)
  4. D.O(V^2)

Explanation

DFS visits each vertex and explores each edge once, giving O(V + E) time complexity.

Report an error in this question

Graph AlgorithmsEasy

Q2. What is a spanning tree of a connected graph?

  1. A.A subgraph with all vertices and all edges
  2. B.A complete subgraph with maximum edges
  3. C.A tree subgraph containing all graph vertices✓ Correct
  4. D.The shortest path tree from one source

Explanation

A spanning tree is a subgraph that includes all vertices of the graph, is connected, and has no cycles (V-1 edges for V vertices).

Report an error in this question

Graph AlgorithmsEasy

Q3. What is a cycle in a graph?

  1. A.An isolated vertex with no edges at all
  2. B.A path starting and ending at the same vertex✓ Correct
  3. C.A straight path between two vertices
  4. D.A tree edge connecting parent to child

Explanation

A cycle is a path in a graph that starts and ends at the same vertex, visiting at least one other vertex, with no repeated edges.

Report an error in this question

Graph AlgorithmsEasy

Q4. What is Depth-First Search (DFS)?

  1. A.A search going deep along each branch first✓ Correct
  2. B.A search only applicable to array structures
  3. C.A search that uses a queue data structure
  4. D.A search that explores all neighbors first

Explanation

DFS explores as far as possible along each branch before backtracking, using a stack (or recursion).

Report an error in this question

Graph AlgorithmsEasy

Q5. What data structure does DFS use?

  1. A.Array structure
  2. B.Stack or recursion✓ Correct
  3. C.Queue structure
  4. D.Heap structure

Explanation

DFS uses a stack (explicitly or via recursion's call stack) to track vertices to visit.

Report an error in this question

Graph AlgorithmsEasy

Q6. What is Breadth-First Search (BFS)?

  1. A.A search that goes as deep as possible first
  2. B.A search only applicable to tree structures
  3. C.A search that uses a stack data structure
  4. D.A search exploring all neighbors at current depth✓ Correct

Explanation

BFS explores all vertices at the current depth level before moving to the next level, using a queue data structure.

Report an error in this question

Graph AlgorithmsEasy

Q7. What is the time complexity of BFS on a graph with V vertices and E edges?

  1. A.O(V + E)✓ Correct
  2. B.O(E)
  3. C.O(V × E)
  4. D.O(V)

Explanation

BFS visits each vertex and explores each edge once, giving O(V + E) time complexity.

Report an error in this question

Graph AlgorithmsEasy

Q8. What data structure does BFS use?

  1. A.Hash table
  2. B.Heap
  3. C.Stack
  4. D.Queue✓ Correct

Explanation

BFS uses a queue to maintain the order of vertices to visit, processing them in FIFO order.

Report an error in this question

Graph AlgorithmsEasy

Q9. Can BFS find the shortest path in an unweighted graph?

  1. A.Yes, BFS can do this✓ Correct
  2. B.No, BFS cannot do this
  3. C.Only in tree structures
  4. D.Only in directed graphs

Explanation

BFS finds the shortest path (minimum number of edges) from a source to all other vertices in an unweighted graph.

Report an error in this question

Graph AlgorithmsEasy

Q10. What is a connected component in an undirected graph?

  1. A.A cycle within the undirected graph
  2. B.A maximal set of vertices all connected by paths✓ Correct
  3. C.An edge connecting two vertices together
  4. D.A single isolated vertex in the graph

Explanation

A connected component is a maximal subset of vertices where every pair of vertices is connected by a path.

Report an error in this question

Graph AlgorithmsMedium

Q11. What is Prim's algorithm used for?

  1. A.Shortest path computation
  2. B.Finding Minimum Spanning Tree✓ Correct
  3. C.Graph coloring assignment
  4. D.Topological sort ordering

Explanation

Prim's algorithm finds the MST by starting from a vertex and greedily adding the cheapest edge connecting the tree to a vertex not yet in the tree.

Report an error in this question

Graph AlgorithmsMedium

Q12. What is topological sorting?

  1. A.Linear ordering of DAG vertices respecting edge directions✓ Correct
  2. B.Sorting edges by their assigned weight values
  3. C.Sorting all vertices by their numeric label values
  4. D.Sorting all vertices by their in-degree values

Explanation

Topological sort produces a linear ordering of vertices in a Directed Acyclic Graph (DAG) where every directed edge goes from earlier to later in the ordering.

Report an error in this question

Graph AlgorithmsMedium

Q13. What type of graph is required for topological sorting?

  1. A.An undirected graph type
  2. B.A complete graph type
  3. C.A weighted graph type
  4. D.Directed Acyclic Graph (DAG)✓ Correct

Explanation

Topological sorting is only possible on Directed Acyclic Graphs (DAGs). A cycle would make it impossible to define a valid ordering.

Report an error in this question

Graph AlgorithmsMedium

Q14. What is the time complexity of Dijkstra's algorithm using a binary heap?

  1. A.O(V × E)
  2. B.O(V + E)
  3. C.O((V + E) log V)✓ Correct
  4. D.O(V^2)

Explanation

Using a binary heap (priority queue), Dijkstra's algorithm runs in O((V + E) log V) time.

Report an error in this question

Graph AlgorithmsMedium

Q15. How can you detect a cycle in a directed graph?

  1. A.By counting edges in the graph
  2. B.Using DFS and checking for back edges✓ Correct
  3. C.Using BFS traversal only
  4. D.By finding the shortest path first

Explanation

A cycle in a directed graph can be detected using DFS: if a back edge (to an ancestor in the DFS tree) is found, a cycle exists.

Report an error in this question

Graph AlgorithmsMedium

Q16. What is the time complexity of the Bellman-Ford algorithm?

  1. A.O(V × E)✓ Correct
  2. B.O(V + E)
  3. C.O(V^2)
  4. D.O(E log V)

Explanation

Bellman-Ford relaxes all E edges V-1 times, giving O(V × E) time complexity.

Report an error in this question

Graph AlgorithmsMedium

Q17. What is Dijkstra's algorithm used for?

  1. A.Finding all cycles in a given graph
  2. B.Finding shortest paths with non-negative weights✓ Correct
  3. C.Sorting all vertices by their degree
  4. D.Finding connected components in a graph

Explanation

Dijkstra's algorithm finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.

Report an error in this question

Graph AlgorithmsMedium

Q18. What is Kruskal's algorithm used for?

  1. A.Shortest path computation
  2. B.Topological sorting of vertices
  3. C.Cycle detection in graphs
  4. D.Finding Minimum Spanning Tree✓ Correct

Explanation

Kruskal's algorithm finds the Minimum Spanning Tree by sorting edges by weight and adding them if they don't form a cycle (using Union-Find).

Report an error in this question

Graph AlgorithmsMedium

Q19. What is the Bellman-Ford algorithm used for?

  1. A.Finding connected components in undirected graphs
  2. B.Finding the Minimum Spanning Tree of a graph
  3. C.Finding shortest paths even with negative weights✓ Correct
  4. D.Topological sorting of directed acyclic graphs

Explanation

Bellman-Ford finds shortest paths from a single source and can handle negative edge weights. It also detects negative weight cycles.

Report an error in this question

Graph AlgorithmsMedium

Q20. What is the Union-Find (Disjoint Set Union) data structure used for?

  1. A.Finding shortest paths between graph vertices
  2. B.Storing key-value pairs with fast lookup
  3. C.Tracking set membership and merging sets efficiently✓ Correct
  4. D.Sorting elements into ordered groups

Explanation

Union-Find efficiently supports union (merge two sets) and find (determine which set an element belongs to) operations, commonly used in Kruskal's MST algorithm.

Report an error in this question

Graph AlgorithmsHard

Q21. What is an articulation point (cut vertex) in a graph?

  1. A.A vertex with no edges connected to it
  2. B.The vertex with the smallest key value
  3. C.A vertex whose removal disconnects the graph✓ Correct
  4. D.A vertex with the maximum degree overall

Explanation

An articulation point is a vertex whose removal (along with its edges) increases the number of connected components in the graph.

Report an error in this question

Graph AlgorithmsHard

Q22. Which algorithms can find Strongly Connected Components?

  1. A.Dijkstra's shortest path algorithm
  2. B.Prim's spanning tree algorithm
  3. C.Kosaraju's and Tarjan's algorithms✓ Correct
  4. D.Floyd-Warshall all-pairs algorithm

Explanation

Kosaraju's algorithm (two DFS passes) and Tarjan's algorithm (single DFS with stack) both find SCCs in O(V + E) time.

Report an error in this question

Graph AlgorithmsHard

Q23. What is the maximum flow problem?

  1. A.Finding the maximum number of vertices
  2. B.Finding maximum flow from source to sink✓ Correct
  3. C.Finding the maximum edge weight in graph
  4. D.Sorting edges by their flow capacity

Explanation

The maximum flow problem finds the greatest rate of flow through a flow network from a source to a sink, respecting edge capacities.

Report an error in this question

Graph AlgorithmsHard

Q24. What is the Ford-Fulkerson method for maximum flow?

  1. A.An iterative method finding augmenting paths until none remain✓ Correct
  2. B.A divide and conquer approach for solving network flows
  3. C.A greedy algorithm for computing the minimum cut value
  4. D.A dynamic programming approach for computing max flow

Explanation

Ford-Fulkerson repeatedly finds augmenting paths from source to sink in the residual graph and increases flow along those paths until no augmenting path exists.

Report an error in this question

Graph AlgorithmsHard

Q25. What is a bridge in a graph?

  1. A.An edge with the maximum weight assigned
  2. B.An edge whose removal disconnects the graph✓ Correct
  3. C.The longest edge in the graph by weight
  4. D.An edge connecting two separate components

Explanation

A bridge is an edge whose removal increases the number of connected components. It can be found using modified DFS in O(V + E) time.

Report an error in this question

Graph AlgorithmsHard

Q26. What are Strongly Connected Components (SCCs) in a directed graph?

  1. A.Maximal subgraphs with mutual reachability✓ Correct
  2. B.Components with no cycles at all
  3. C.Components with the most vertices total
  4. D.Components with the most edges overall

Explanation

An SCC is a maximal set of vertices where every pair of vertices is mutually reachable via directed paths.

Report an error in this question

Graph AlgorithmsHard

Q27. What does the Max-Flow Min-Cut theorem state?

  1. A.Maximum flow equals the number of all paths
  2. B.Maximum flow equals minimum edge weight
  3. C.Maximum flow equals the minimum cut capacity✓ Correct
  4. D.Minimum cut equals the total number of edges

Explanation

The Max-Flow Min-Cut theorem states that the maximum flow from source to sink equals the minimum total capacity of edges in a cut that separates source and sink.

Report an error in this question

Graph AlgorithmsHard

Q28. What is the time complexity of Dijkstra's algorithm with a Fibonacci heap?

  1. A.O(V × E)
  2. B.O((V + E) log V)
  3. C.O(V log V + E)✓ Correct
  4. D.O(V^2)

Explanation

Using a Fibonacci heap, Dijkstra's algorithm achieves O(V log V + E) time, improving the decrease-key operation to amortized O(1).

Report an error in this question

Graph AlgorithmsHard

Q29. What is the Floyd-Warshall algorithm?

  1. A.An all-pairs shortest path DP algorithm✓ Correct
  2. B.A minimum spanning tree algorithm only
  3. C.A single-source shortest path algorithm
  4. D.A graph coloring assignment algorithm

Explanation

Floyd-Warshall computes shortest paths between all pairs of vertices using dynamic programming in O(V^3) time.

Report an error in this question

Graph AlgorithmsHard

Q30. What is the time complexity of Floyd-Warshall algorithm?

  1. A.O(V^3)✓ Correct
  2. B.O(V^2)
  3. C.O(V × E)
  4. D.O(V + E)

Explanation

Floyd-Warshall uses three nested loops over V vertices, giving O(V^3) time complexity.

Report an error in this question

More Data Structures & Algorithms Topics

Foundations of DS & Algorithms

Practice MCQs with explanations

Linear Data Structures

Practice MCQs with explanations

Non-Linear Data Structures

Practice MCQs with explanations

Searching Algorithms

Practice MCQs with explanations

Sorting Algorithms

Practice MCQs with explanations

Hashing

Practice MCQs with explanations

Ready to test yourself on Graph Algorithms?

Take a timed quiz drawn from 210+ questions on this topic. No signup required — your progress saves in your browser.

Start Graph Algorithms Quiz