Q.1 Which of the following is NOT a type of graph?
Directed Graph
Undirected Graph
Weighted Graph
Sequential Graph
Explanation - Directed, undirected, and weighted are standard types of graphs. 'Sequential Graph' is not a recognized type.
Correct answer is: Sequential Graph
Q.2 In a weighted graph, the weight of an edge represents:
The number of vertices
The cost or distance between vertices
The degree of a vertex
The number of edges in the graph
Explanation - Weighted graphs assign a numerical value (weight) to each edge representing cost, distance, or capacity.
Correct answer is: The cost or distance between vertices
Q.3 Which graph traversal algorithm uses a queue data structure?
Depth-First Search (DFS)
Breadth-First Search (BFS)
Dijkstra's Algorithm
Prim's Algorithm
Explanation - BFS explores nodes level by level and uses a queue to keep track of the next vertices to visit.
Correct answer is: Breadth-First Search (BFS)
Q.4 Which of the following statements about DFS is true?
DFS visits nodes in a breadth-wise manner
DFS uses a stack or recursion
DFS cannot detect cycles
DFS always finds the shortest path
Explanation - DFS explores as far as possible along each branch and uses a stack (explicit or via recursion).
Correct answer is: DFS uses a stack or recursion
Q.5 In an undirected graph, the sum of all vertex degrees is always:
Equal to the number of vertices
Twice the number of edges
Equal to the number of edges
Odd
Explanation - Each edge contributes 2 to the total degree count in an undirected graph.
Correct answer is: Twice the number of edges
Q.6 Which of the following algorithms finds the shortest path in a weighted graph without negative weights?
Bellman-Ford Algorithm
Dijkstra's Algorithm
Kruskal's Algorithm
DFS
Explanation - Dijkstra's algorithm efficiently computes shortest paths from a source to all vertices for non-negative weights.
Correct answer is: Dijkstra's Algorithm
Q.7 What is the time complexity of BFS on a graph represented using adjacency lists?
O(V+E)
O(V^2)
O(E^2)
O(V*E)
Explanation - BFS visits every vertex and edge once, so the complexity is proportional to vertices + edges.
Correct answer is: O(V+E)
Q.8 A graph with no cycles is called a:
Tree
Cyclic Graph
Directed Graph
Weighted Graph
Explanation - A tree is an acyclic connected graph. Any cycle in a graph disqualifies it from being a tree.
Correct answer is: Tree
Q.9 Kruskal’s algorithm is used for:
Shortest path
Minimum spanning tree
Graph coloring
Cycle detection
Explanation - Kruskal's algorithm constructs a minimum spanning tree by selecting edges in increasing weight order while avoiding cycles.
Correct answer is: Minimum spanning tree
Q.10 Prim’s algorithm differs from Kruskal’s algorithm because it:
Starts with a single vertex and grows the MST
Sorts all edges first
Can work only for unweighted graphs
Uses DFS internally
Explanation - Prim's algorithm grows the minimum spanning tree from an initial vertex, adding the smallest edge connecting to the tree.
Correct answer is: Starts with a single vertex and grows the MST
Q.11 Which data structure is most commonly used for implementing Dijkstra’s algorithm?
Queue
Stack
Priority Queue
Linked List
Explanation - A priority queue allows selection of the vertex with the smallest tentative distance efficiently.
Correct answer is: Priority Queue
Q.12 Topological sorting is applicable to which type of graph?
Undirected Graph
Cyclic Graph
Directed Acyclic Graph (DAG)
Weighted Graph
Explanation - Topological sorting orders vertices linearly such that every directed edge u → v, u comes before v. This is only possible in DAGs.
Correct answer is: Directed Acyclic Graph (DAG)
Q.13 Which algorithm can detect negative weight cycles in a graph?
Dijkstra's Algorithm
Bellman-Ford Algorithm
Prim's Algorithm
DFS
Explanation - Bellman-Ford can handle negative weights and detect negative cycles by checking for further distance improvements after |V|-1 iterations.
Correct answer is: Bellman-Ford Algorithm
Q.14 In an adjacency matrix of a graph with V vertices, the space complexity is:
O(V)
O(E)
O(V+E)
O(V^2)
Explanation - An adjacency matrix stores V*V entries to indicate edge presence between all pairs of vertices.
Correct answer is: O(V^2)
Q.15 Which of the following is true for a complete graph with n vertices?
It has exactly n edges
It has n(n-1)/2 edges
It is always directed
It cannot have a cycle
Explanation - A complete undirected graph has an edge between every pair of vertices: n(n-1)/2 edges.
Correct answer is: It has n(n-1)/2 edges
Q.16 Which of these is NOT a typical application of graph algorithms?
Network routing
Social network analysis
Sorting an array
Task scheduling
Explanation - Graphs are used for network analysis, scheduling, and relationships, but sorting is not a graph problem.
Correct answer is: Sorting an array
Q.17 The in-degree of a vertex in a directed graph is:
Number of edges leaving the vertex
Number of edges entering the vertex
Number of adjacent vertices
Always zero
Explanation - In-degree counts how many edges point to a given vertex in a directed graph.
Correct answer is: Number of edges entering the vertex
Q.18 A bipartite graph is a graph where:
All vertices are connected
Vertices can be divided into two sets with edges only between sets
Every vertex has equal degree
It contains a cycle of odd length
Explanation - Bipartite graphs have two disjoint vertex sets and edges exist only between the sets, not within a set.
Correct answer is: Vertices can be divided into two sets with edges only between sets
Q.19 Floyd-Warshall algorithm is used for:
Single source shortest path
All pairs shortest path
Minimum spanning tree
Topological sorting
Explanation - Floyd-Warshall computes shortest paths between all pairs of vertices using dynamic programming.
Correct answer is: All pairs shortest path
Q.20 Which of the following is true about a strongly connected directed graph?
There is a path between any two vertices in both directions
There are no cycles
It is always acyclic
Every vertex has degree 1
Explanation - Strong connectivity in a directed graph means each vertex can reach every other vertex via a directed path.
Correct answer is: There is a path between any two vertices in both directions
Q.21 Which algorithm can be used to find strongly connected components of a graph?
Kruskal's Algorithm
Tarjan's Algorithm
Prim's Algorithm
Dijkstra's Algorithm
Explanation - Tarjan’s algorithm identifies strongly connected components efficiently using DFS and low-link values.
Correct answer is: Tarjan's Algorithm
Q.22 Which graph representation is most efficient for sparse graphs?
Adjacency matrix
Adjacency list
Edge list
Incidence matrix
Explanation - Adjacency lists use space proportional to vertices + edges, making them more efficient than matrices for sparse graphs.
Correct answer is: Adjacency list
Q.23 In Dijkstra's algorithm, what happens if a graph contains negative edge weights?
Algorithm works normally
Algorithm may produce incorrect results
Algorithm finds negative cycles automatically
Algorithm converts weights to positive
Explanation - Dijkstra’s algorithm assumes non-negative weights; negative weights can lead to wrong shortest paths.
Correct answer is: Algorithm may produce incorrect results
Q.24 Which algorithm is commonly used for finding a cycle in a directed graph?
DFS with recursion stack
BFS with queue
Dijkstra's Algorithm
Prim's Algorithm
Explanation - DFS keeps track of the recursion stack to detect back edges, which indicate cycles in a directed graph.
Correct answer is: DFS with recursion stack