Graphs - Practice MCQs for CCAT

Correct Answer: B - BFS

BFS finds shortest path in unweighted graphs by exploring level by level.

Correct Answer: C - Shortest path from single source

Dijkstra finds shortest path from single source to all other vertices.

Correct Answer: A - Stack

DFS uses stack (or recursion which uses call stack).

Correct Answer: B - n(n-1)/2

Maximum edges in simple undirected graph = n(n-1)/2 (complete graph).

Correct Answer: A - DAG only

Topological sort works only on Directed Acyclic Graphs (DAG).

Correct Answer: B - Minimum Spanning Tree

Kruskal's finds MST using greedy approach, selecting smallest edges.

Correct Answer: D - O(V+E)

BFS visits all vertices and edges once, taking O(V+E) time.

Correct Answer: D - V-1

Minimum edges for connected graph is V-1 (a tree).

Correct Answer: D - O(n²)

Adjacency matrix is n×n, using O(n²) space.

Correct Answer: C - MST

Prim's algorithm finds Minimum Spanning Tree.

Correct Answer: C - Bellman-Ford

Bellman-Ford algorithm can detect negative weight cycles in a graph.

Correct Answer: B - All pairs shortest paths

Floyd-Warshall finds shortest paths between all pairs of vertices.

Correct Answer: B - O(V³)

Floyd-Warshall uses three nested loops, giving O(V³) complexity.

Correct Answer: B - Odd length

A graph is bipartite if and only if it contains no odd-length cycles.

Correct Answer: C - Kosaraju or Tarjan algorithm

Kosaraju's and Tarjan's algorithms find strongly connected components in directed graphs.

Correct Answer: D - Vertex whose removal disconnects graph

An articulation point (cut vertex) is a vertex whose removal increases connected components.

Correct Answer: A - Incoming edges count

In-degree is the number of edges coming into a vertex.

Correct Answer: B - Min-Heap/Priority Queue

Min-heap or priority queue gives O((V+E)log V) complexity for Dijkstra.

Correct Answer: D - n-1 edges

A tree is a connected acyclic graph with exactly n-1 edges for n vertices.

Correct Answer: A - Presence of cycle

A back edge (edge to ancestor) in DFS tree indicates a cycle in the graph.

Correct Answer: A - Queue

BFS uses a queue to explore all vertices at the current depth level before moving to vertices at the next depth level.

Correct Answer: B - Stack

DFS uses a stack (either explicitly or via recursion's call stack) to explore as deep as possible along each branch before backtracking.

Correct Answer: D - O(V + E)

BFS visits each vertex once O(V) and examines each edge once O(E), giving a total time complexity of O(V + E).

Correct Answer: A - BFS

BFS finds the shortest path in an unweighted graph because it explores nodes level by level, ensuring the first time a node is reached is via the shortest path.

Correct Answer: D - Graphs with negative edge weights

Dijkstra's algorithm assumes all edge weights are non-negative. Negative edge weights can cause it to produce incorrect shortest paths.

Correct Answer: D - Bellman-Ford algorithm

The Bellman-Ford algorithm can handle negative edge weights and also detect negative weight cycles, unlike Dijkstra's algorithm.

Correct Answer: C - n(n-1)/2

In a complete undirected graph, every pair of distinct vertices is connected by an edge. The number of such pairs is C(n,2) = n(n-1)/2.

Correct Answer: C - It is a connected acyclic graph

A tree is defined as a connected acyclic graph. It has exactly n-1 edges for n vertices and no cycles.

Correct Answer: B - Minimum Spanning Tree

Kruskal's algorithm finds the Minimum Spanning Tree (MST) of a connected weighted graph by greedily adding edges in order of increasing weight.

Correct Answer: A - Greedy

Prim's algorithm uses a greedy approach, growing the MST by always adding the minimum weight edge connecting the tree to a vertex not yet in the tree.

Correct Answer: A - O(V²)

An adjacency matrix requires a V × V 2D array, resulting in O(V²) space regardless of the number of edges.

Correct Answer: B - Adjacency list

An adjacency list uses O(V + E) space, which is much less than O(V²) of an adjacency matrix when the graph is sparse (E << V²).

Correct Answer: D - Directed Acyclic Graphs (DAGs)

Topological sorting is only possible for Directed Acyclic Graphs (DAGs). If a graph has a cycle, no valid topological ordering exists.

Correct Answer: A - A cycle

A back edge in DFS connects a vertex to one of its ancestors in the DFS tree, which indicates the presence of a cycle in a directed graph.

Correct Answer: B - O(E log V)

Using a binary heap (min-priority queue), Dijkstra's algorithm runs in O(E log V) time, as each edge relaxation involves a heap operation of O(log V).

Correct Answer: A - Bellman-Ford algorithm

Bellman-Ford can detect negative weight cycles by running one extra iteration. If any distance is updated in the V-th iteration, a negative cycle exists.

Correct Answer: C - Tree

A connected graph with V vertices and exactly V-1 edges is a tree. It has no cycles and removing any edge disconnects it.

Correct Answer: B - n(n-1)

In a directed graph without self-loops, each ordered pair of distinct vertices can have an edge. There are n(n-1) such ordered pairs.

Correct Answer: C - Floyd-Warshall algorithm

Floyd-Warshall algorithm computes shortest paths between all pairs of vertices using dynamic programming with O(V³) time complexity.

Correct Answer: C - The number of vertices adjacent to it

The degree of a vertex in an undirected graph is the number of edges incident to it, which equals the number of adjacent vertices.

Correct Answer: C - Twice the number of edges

By the Handshaking Lemma, the sum of degrees of all vertices in an undirected graph equals 2 × E (twice the number of edges), since each edge contributes to the degree of two vertices.

Correct Answer: D - Disjoint Set (Union-Find)

Kruskal's algorithm uses the Disjoint Set (Union-Find) data structure to efficiently check whether adding an edge would create a cycle.

Correct Answer: C - Can be colored with 2 colors such that no adjacent vertices share a color

A bipartite graph can be divided into two sets such that every edge connects a vertex from one set to the other, equivalent to being 2-colorable.

Correct Answer: A - O(VE)

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

Correct Answer: D - Disconnects the graph

An articulation point (or cut vertex) is a vertex whose removal increases the number of connected components, disconnecting the graph.

Correct Answer: C - Both BFS and DFS

Both BFS and DFS can check bipartiteness by attempting a 2-coloring. If a conflict is found (adjacent vertices same color), the graph is not bipartite.

Correct Answer: A - V - 1

A connected graph with V vertices requires at least V-1 edges, forming a tree structure.

Correct Answer: B - It connects all vertices with minimum total edge weight

An MST connects all V vertices using V-1 edges with the minimum possible total edge weight, without forming any cycle.

Correct Answer: D - Avoid revisiting and infinite loops

Marking vertices as visited in BFS prevents revisiting them, which avoids infinite loops (especially in cyclic graphs) and ensures each vertex is processed once.

Correct Answer: A - O(V³)

Floyd-Warshall uses three nested loops over V vertices, resulting in O(V³) time complexity.