Graphs — Practice MCQs for CCAT

Correct Answer: B — BFS

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

Correct Answer: B — Shortest path from single source

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

Correct Answer: B — Stack

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

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

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

Correct Answer: C — 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: C — O(V+E)

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

Correct Answer: B — V-1

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

Correct Answer: B — O(n²)

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

Correct Answer: B — 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: B — Kosaraju or Tarjan algorithm

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

Correct Answer: B — Vertex whose removal disconnects graph

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

Correct Answer: B — Incoming edges count

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

Correct Answer: C — Min-Heap/Priority Queue

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

Correct Answer: B — n-1 edges

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

Correct Answer: B — Presence of cycle

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