Graphs — Part 1 MCQs with Explanations

A directed graph has edges with direction, while an undirected graph does not. is the correct answer to “What is the primary difference between a directed graph and an undirected graph”. This question is standard in competitive examination syllabi for Graphs.

O(V2) is the correct answer to “What is the time complexity of performing a depth-first search (DFS) on a graph using an adjacency matrix”. This question is standard in competitive examination syllabi for Graphs.

It can be colored using two colors such that no two adjacent vertices share the same color. is the correct answer to “Which of the following is true about a bipartite graph”. This question is standard in competitive examination syllabi for Graphs.

A path that starts and ends at the same vertex with no other repetitions. is the correct answer to “What is a cycle in a graph”. This question is standard in competitive examination syllabi for Graphs.

To store the edges and their weights between all pairs of vertices. is the correct answer to “What is the purpose of the adjacency matrix in graph representation”. This question is standard in competitive examination syllabi for Graphs.

Breadth-First Search (BFS) is the correct answer to “Which traversal algorithm would you use to find the shortest path in an unweighted graph”. This question is standard in competitive examination syllabi for Graphs.

When there are negative weight edges. is the correct answer to “In which scenario is Dijkstra's algorithm not suitable for finding the shortest path”. This question is standard in competitive examination syllabi for Graphs.

Every pair of vertices is connected by a unique edge. is the correct answer to “What is the main characteristic of a complete graph”. This question is standard in competitive examination syllabi for Graphs.

A subgraph that includes all vertices and is connected without any cycles. is the correct answer to “What is a spanning tree of a graph”. This question is standard in competitive examination syllabi for Graphs.

By checking if there is a back edge during traversal. is the correct answer to “How can you determine if a graph contains a cycle using DFS”. This question is standard in competitive examination syllabi for Graphs.

Kruskal's Algorithm is the correct answer to “Which algorithm is used to find the minimum spanning tree in a graph”. This question is standard in competitive examination syllabi for Graphs.

The shortest path cannot be computed reliably. is the correct answer to “In a weighted graph, what does a negative weight cycle indicate for shortest path algorithms”. This question is standard in competitive examination syllabi for Graphs.

O(V + E) is the correct answer to “What is the time complexity of the BFS algorithm for a graph represented using an adjacency list”. This question is standard in competitive examination syllabi for Graphs.

By considering all pairs of vertices and iteratively updating shortest paths. is the correct answer to “How does the Floyd-Warshall algorithm compute shortest paths in a graph”. This question is standard in competitive examination syllabi for Graphs.

To efficiently extract the vertex with the minimum distance. is the correct answer to “What is the primary purpose of using a priority queue in graph algorithms like Dijkstra's”. This question is standard in competitive examination syllabi for Graphs.

Tarjan's Algorithm is the correct answer to “Which of the following algorithms is used to detect cycles in a directed graph”. This question is standard in competitive examination syllabi for Graphs.

A linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v. is the correct answer to “What is a topological sort in a directed graph”. This question is standard in competitive examination syllabi for Graphs.

Queue is the correct answer to “Which data structure is commonly used to implement the BFS algorithm”. This question is standard in competitive examination syllabi for Graphs.

O(V + E) is the correct answer to “What is the time complexity of finding all reachable nodes from a given node in an undirected graph using DFS”. This question is standard in competitive examination syllabi for Graphs.

When the graph is dense. is the correct answer to “In which of the following scenarios is Prim's algorithm more efficient than Kruskal's algorithm”. This question is standard in competitive examination syllabi for Graphs.

Directed Acyclic Graph (DAG) is the correct answer to “What type of graph can be used to model hierarchical data structures such as organizational charts”. This question is standard in competitive examination syllabi for Graphs.

To find the shortest path from a single source to all other vertices, even with negative weights. is the correct answer to “What is the primary goal of the Bellman-Ford algorithm”. This question is standard in competitive examination syllabi for Graphs.

Floyd-Warshall Algorithm is the correct answer to “Which of the following algorithms can be used to find all-pairs shortest paths in a graph”. This question is standard in competitive examination syllabi for Graphs.

There is a path from every vertex to every other vertex. is the correct answer to “What is the characteristic of a strongly connected component in a directed graph”. This question is standard in competitive examination syllabi for Graphs.

The number of edges incoming to a vertex. is the correct answer to “What does the term "in-degree" refer to in the context of a directed graph”. This question is standard in competitive examination syllabi for Graphs.

Updating the shortest path estimate if a shorter path is found. is the correct answer to “In a graph with weighted edges, what does the term "relaxation" refer to in shortest path algorithms”. This question is standard in competitive examination syllabi for Graphs.

Max-Flow Min-Cut Theorem is the correct answer to “Which of the following methods is used to find the minimum cut in a graph”. This question is standard in competitive examination syllabi for Graphs.

It represents a partition of the vertices into two sets, where the minimum cut is the smallest set of edges that, if removed, would disconnect the source from the sink. is the correct answer to “What is the significance of the "cut" in the context of the Max-Flow Min-Cut Theorem”. This question is standard in competitive examination syllabi for Graphs.

Depth-First Search (DFS) is the correct answer to “Which traversal method is best for finding connected components in an undirected graph”. This question is standard in competitive examination syllabi for Graphs.

O(V + E) is the correct answer to “What is the time complexity of performing a DFS traversal on a graph represented using an adjacency list”. This question is standard in competitive examination syllabi for Graphs.

O(V2) is the correct answer to “What is the space complexity of storing a graph using an adjacency matrix”. This question is standard in competitive examination syllabi for Graphs.

O(1) is the correct answer to “What is the time complexity of adding an edge in an adjacency list representation of a graph”. This question is standard in competitive examination syllabi for Graphs.

The cost or distance between two vertices. is the correct answer to “In a weighted graph, what does the edge weight represent”. This question is standard in competitive examination syllabi for Graphs.

Kosaraju's Algorithm is the correct answer to “Which algorithm is used to find the strongly connected components of a directed graph”. This question is standard in competitive examination syllabi for Graphs.

O(V + E) is the correct answer to “What is the time complexity of performing a BFS on a graph with V vertices and E edges using an adjacency list”. This question is standard in competitive examination syllabi for Graphs.

It is a connected acyclic graph. is the correct answer to “What is the characteristic of a tree that makes it a special type of graph”. This question is standard in competitive examination syllabi for Graphs.

Floyd-Warshall Algorithm is the correct answer to “Which of the following graph algorithms is used to find the shortest path between all pairs of vertices”. This question is standard in competitive examination syllabi for Graphs.

It can handle them but not negative weight cycles. is the correct answer to “How does the Bellman-Ford algorithm handle negative weight edges”. This question is standard in competitive examination syllabi for Graphs.

To store a list of adjacent vertices for each vertex. is the correct answer to “What is the purpose of the adjacency list in graph representation”. This question is standard in competitive examination syllabi for Graphs.

Twice the number of edges. is the correct answer to “In an undirected graph, what is the sum of the degrees of all vertices equal to”. This question is standard in competitive examination syllabi for Graphs.