C Programming Graph MCQs
Basic Graph Concepts (30 Questions)
1. What is a graph in data structures?
A) A collection of nodes with no connections
B) A collection of nodes (vertices) connected by edges
C) A hierarchical data structure
D) A linear data structure
Answer: B) A collection of nodes (vertices) connected by edges
A graph consists of a finite set of vertices and edges that connect pairs of vertices.
2. Which of these is NOT a graph representation?
A) Adjacency Matrix
B) Adjacency List
C) Incidence Matrix
D) Binary Search Tree
Answer: D) Binary Search Tree
Binary Search Tree is a different data structure, not a graph representation method.
3. What is the time complexity of checking if an edge exists in an adjacency matrix?
A) O(1)
B) O(V)
C) O(E)
D) O(V+E)
Answer: A) O(1)
Adjacency matrix allows constant time edge lookups by accessing matrix[i][j].
4. What is the space complexity of an adjacency list for a graph with V vertices and E edges?
A) O(V)
B) O(V+E)
C) O(V²)
D) O(E)
Answer: B) O(V+E)
Adjacency list requires space for all vertices and all edges.
5. What is a connected graph?
A) A graph where all vertices have even degree
B) A graph with no cycles
C) A graph where there's a path between any two vertices
D) A graph with V-1 edges
Answer: C) A graph where there's a path between any two vertices
In a connected graph, every pair of vertices is connected by a path.
6. What is the maximum number of edges in a directed graph with n vertices?
A) n(n-1)/2
B) n²
C) n(n-1)
D) 2ⁿ
Answer: C) n(n-1)
In a directed graph, each vertex can have an edge to every other vertex (n*(n-1)).
7. Which traversal uses a queue data structure?
A) Depth First Search
B) Breadth First Search
C) Both A and B
D) Neither A nor B
Answer: B) Breadth First Search
BFS uses a queue to explore all neighbors at the present depth before moving deeper.
8. What is the time complexity of BFS on a graph with V vertices and E edges?
A) O(V)
B) O(E)
C) O(V+E)
D) O(V*E)
Answer: C) O(V+E)
BFS visits every vertex and edge exactly once in worst case.
9. Which algorithm is used to find the shortest path in an unweighted graph?
A) Dijkstra's algorithm
B) Bellman-Ford algorithm
C) BFS
D) Floyd-Warshall algorithm
Answer: C) BFS
BFS naturally finds the shortest path in unweighted graphs by exploring level by level.
10. What is a cycle in a graph?
A) A path that starts and ends at the same vertex
B) A graph with no repeated edges
C) A graph where all vertices have even degree
D) A traversal that visits all vertices
Answer: A) A path that starts and ends at the same vertex
A cycle is a path of length ≥ 1 that starts and ends at the same vertex with no repeated edges.
11. What is a tree in graph theory?
A) A connected graph with cycles
B) A connected acyclic graph
C) A complete graph
D) A bipartite graph
Answer: B) A connected acyclic graph
A tree is an undirected graph that is connected and has no cycles.
12. How many edges does a tree with n vertices have?
A) n
B) n-1
C) n²
D) log(n)
Answer: B) n-1
A tree with n vertices always has exactly n-1 edges.
13. What is a bipartite graph?
A) A graph with two edges between every pair of vertices
B) A graph whose vertices can be divided into two disjoint sets
C) A graph with exactly two vertices
D) A graph with edges of two different colors
Answer: B) A graph whose vertices can be divided into two disjoint sets
In a bipartite graph, every edge connects a vertex from one set to the other.
14. Which algorithm is used to detect cycles in an undirected graph?
A) Dijkstra's algorithm
B) Union-Find (Disjoint Set)
C) Prim's algorithm
D) Floyd-Warshall algorithm
Answer: B) Union-Find (Disjoint Set)
Union-Find can efficiently detect cycles during graph construction.
15. What is the time complexity of DFS on a graph with V vertices and E edges?
A) O(V)
B) O(E)
C) O(V+E)
D) O(V*E)
Answer: C) O(V+E)
DFS visits every vertex and edge exactly once in worst case.
16. What is a complete graph?
A) A graph with no cycles
B) A graph where every pair of distinct vertices is connected
C) A graph with equal number of vertices and edges
D) A graph that can be colored with two colors
Answer: B) A graph where every pair of distinct vertices is connected
In a complete graph, every pair of distinct vertices is connected by a unique edge.
17. How many edges does a complete graph with n vertices have?
A) n
B) n-1
C) n(n-1)/2
D) n²
Answer: C) n(n-1)/2
Each of the n vertices connects to n-1 others, divided by 2 to avoid double-counting.
18. What is the degree of a vertex?
A) The number of edges in the graph
B) The number of edges connected to the vertex
C) The distance from the root
D) The number of cycles passing through the vertex
Answer: B) The number of edges connected to the vertex
Degree is the count of edges incident to the vertex (in-degree and out-degree for directed graphs).
19. What is a weighted graph?
A) A graph with edges having numerical values
B) A graph with more edges than vertices
C) A complete graph
D) A graph with vertices having numerical values
Answer: A) A graph with edges having numerical values
In a weighted graph, each edge has an associated numerical value (weight).
20. What is an Eulerian path?
A) A path that visits every vertex exactly once
B) A path that visits every edge exactly once
C) The shortest path between two vertices
D) A path that starts and ends at the same vertex
Answer: B) A path that visits every edge exactly once
An Eulerian path traverses every edge exactly once (Eulerian circuit if it starts and ends at same vertex).
21. What is a Hamiltonian path?
A) A path that visits every vertex exactly once
B) A path that visits every edge exactly once
C) The shortest path between two vertices
D) A path that starts and ends at the same vertex
Answer: A) A path that visits every vertex exactly once
A Hamiltonian path visits each vertex exactly once (Hamiltonian cycle if it's a cycle).
22. Which algorithm finds the shortest path in a weighted graph with no negative edges?
A) BFS
B) Dijkstra's algorithm
C) Bellman-Ford algorithm
D) Floyd-Warshall algorithm
Answer: B) Dijkstra's algorithm
Dijkstra's algorithm efficiently finds shortest paths in graphs with non-negative edge weights.
23. What is the time complexity of Dijkstra's algorithm with a binary heap?
A) O(V)
B) O(V log V)
C) O(V log V + E)
D) O(V²)
Answer: C) O(V log V + E)
With binary heap, Dijkstra's has O((V+E)log V) complexity which simplifies to O(E log V) for connected graphs.
24. Which algorithm can handle negative weight edges in graphs?
A) Dijkstra's algorithm
B) Bellman-Ford algorithm
C) Prim's algorithm
D) Kruskal's algorithm
Answer: B) Bellman-Ford algorithm
Bellman-Ford can handle negative weights and detect negative weight cycles.
25. What is the time complexity of Bellman-Ford algorithm?
A) O(V)
B) O(V log V)
C) O(VE)
D) O(V²)
Answer: C) O(VE)
Bellman-Ford relaxes all edges V-1 times, resulting in O(VE) complexity.
26. Which algorithm finds all pairs shortest paths?
A) Dijkstra's algorithm
B) Bellman-Ford algorithm
C) Floyd-Warshall algorithm
D) Prim's algorithm
Answer: C) Floyd-Warshall algorithm
Floyd-Warshall computes shortest paths between all pairs of vertices.
27. What is the time complexity of Floyd-Warshall algorithm?
A) O(V log V)
B) O(V²)
C) O(V³)
D) O(V⁴)
Answer: C) O(V³)
Floyd-Warshall uses three nested loops over all vertices, resulting in O(V³) time.
28. Which algorithm finds a minimum spanning tree?
A) Dijkstra's algorithm
B) Bellman-Ford algorithm
C) Prim's algorithm
D) Floyd-Warshall algorithm
Answer: C) Prim's algorithm
Prim's algorithm grows a minimum spanning tree from a starting vertex.
29. What is the time complexity of Prim's algorithm with adjacency matrix?
A) O(V log V)
B) O(V²)
C) O(E log V)
D) O(E + V log V)
Answer: B) O(V²)
With adjacency matrix, Prim's algorithm runs in O(V²) time.
30. Which algorithm uses a greedy approach to find MST?
A) Both Prim's and Kruskal's
B) Only Prim's
C) Only Kruskal's
D) Neither
Answer: A) Both Prim's and Kruskal's
Both Prim's and Kruskal's algorithms use greedy approaches to find minimum spanning trees.
Graph Algorithms in C (20 Questions)
1. Which data structure is typically used for DFS implementation?
A) Queue
B) Stack
C) Priority Queue
D) Heap
Answer: B) Stack
DFS uses a stack (either explicitly or via recursion) to explore as far as possible along each branch.
2. What is the output of BFS on a complete graph with 3 vertices?
A) 0, 1, 2
B) 0, 2, 1
C) Depends on starting vertex and edge order
D) 1, 0, 2
Answer: C) Depends on starting vertex and edge order
BFS output depends on the starting vertex and the order of edges in the adjacency list.
3. Which algorithm would you use to find connected components in an undirected graph?
A) Dijkstra's
B) BFS or DFS
C) Floyd-Warshall
D) Prim's
Answer: B) BFS or DFS
Both BFS and DFS can traverse connected components in undirected graphs.
4. How would you detect a cycle in a directed graph?
A) Using Union-Find
B) Using DFS with recursion stack tracking
C) Using BFS
D) Both A and B
Answer: B) Using DFS with recursion stack tracking
For directed graphs, DFS with recursion stack tracking is needed (Union-Find works only for undirected).
5. What is topological sorting?
A) Sorting vertices by their degree
B) Linear ordering of vertices where for every edge u→v, u comes before v
C) Sorting edges by weight
D) Coloring vertices with minimum colors
Answer: B) Linear ordering of vertices where for every edge u→v, u comes before v
Topological sort arranges vertices in a linear order respecting all edge directions.
6. Which algorithm is used for topological sorting?
A) BFS (Kahn's algorithm)
B) DFS with finishing times
C) Both A and B
D) Dijkstra's algorithm
Answer: C) Both A and B
Both Kahn's algorithm (BFS-based) and DFS with finishing times can perform topological sort.
7. What is the time complexity of Kruskal's algorithm?
A) O(V log V)
B) O(E log V)
C) O(E log E)
D) O(V²)
Answer: C) O(E log E)
Kruskal's algorithm sorts all edges (O(E log E)) and uses Union-Find operations (O(α(V)) per op).
8. What is the key difference between Prim's and Kruskal's algorithms?
A) Prim's grows one tree, Kruskal's grows multiple trees
B) Prim's works for directed graphs
C) Kruskal's is faster
D) Prim's can handle negative weights
Answer: A) Prim's grows one tree, Kruskal's grows multiple trees
Prim's maintains a single tree, while Kruskal's can have multiple disjoint trees that merge.
9. Which graph algorithm uses dynamic programming?
A) Dijkstra's
B) Bellman-Ford
C) Floyd-Warshall
D) Both B and C
Answer: D) Both B and C
Both Bellman-Ford and Floyd-Warshall use dynamic programming approaches.
10. What is the key idea behind Dijkstra's algorithm?
A) Relax all edges V-1 times
B) Always extend the shortest path found so far
C) Use divide and conquer
D) Sort edges by weight
Answer: B) Always extend the shortest path found so far
Dijkstra's greedily extends the shortest known path at each step.
11. What is the key idea behind Bellman-Ford algorithm?
A) Relax all edges V-1 times
B) Always extend the shortest path found so far
C) Use divide and conquer
D) Sort edges by weight
Answer: A) Relax all edges V-1 times
Bellman-Ford relaxes all edges repeatedly to ensure shortest paths are found.
12. What is the key idea behind Floyd-Warshall algorithm?
A) Consider all vertices as intermediate points
B) Relax all edges V-1 times
C) Use a priority queue
D) Sort edges by weight
Answer: A) Consider all vertices as intermediate points
Floyd-Warshall considers each vertex as a potential intermediate point in paths between other vertices.
13. Which graph algorithm would you use to find articulation points?
A) BFS
B) DFS with discovery times and low values
C) Dijkstra's
D) Kruskal's
Answer: B) DFS with discovery times and low values
Finding articulation points requires tracking discovery times and low values during DFS.
14. What is a strongly connected component in a directed graph?
A) A cycle
B) A maximal subgraph where every pair of vertices is mutually reachable
C) A complete subgraph
D) A tree
Answer: B) A maximal subgraph where every pair of vertices is mutually reachable
In a strongly connected component, there's a path from any vertex to any other vertex.
15. Which algorithm finds strongly connected components?
A) Kosaraju's algorithm
B) Tarjan's algorithm
C) Both A and B
D) Dijkstra's algorithm
Answer: C) Both A and B
Both Kosaraju's and Tarjan's algorithms can find strongly connected components.
16. What is the time complexity of Kosaraju's algorithm?
A) O(V)
B) O(V log V)
C) O(V+E)
D) O(V²)
Answer: C) O(V+E)
Kosaraju's performs two DFS traversals, each O(V+E) time.
17. What is the key step in Kosaraju's algorithm?
A) Sorting edges by weight
B) Performing DFS on the reversed graph
C) Using a priority queue
D) Relaxing edges repeatedly
Answer: B) Performing DFS on the reversed graph
Kosaraju's algorithm involves DFS on the original graph, then on the transposed graph.
18. What is a bipartite graph check algorithm's time complexity?
A) O(V)
B) O(V log V)
C) O(V+E)
D) O(V²)
Answer: C) O(V+E)
Bipartite check can be done with BFS/DFS coloring in O(V+E) time.
19. Which algorithm would you use to find the maximum flow in a network?
A) Ford-Fulkerson
B) Edmonds-Karp
C) Dinic's
D) All of the above
Answer: D) All of the above
All these algorithms solve the maximum flow problem with different approaches.
20. What is the time complexity of Edmonds-Karp algorithm?
A) O(V E)
B) O(V E²)
C) O(V² E)
D) O(V³)
Answer: B) O(V E²)
Edmonds-Karp (BFS-based Ford-Fulkerson) runs in O(V E²) time.
Related Graph Resources