1.Which of the following correctly defines a directed graph?
A) A graph where edges have a direction associated with them
B) A graph where all edges have the same weight
C) A graph where vertices have labels associated with them
D) A graph where edges connect vertices without any direction
Answer: A) A graph where edges have a direction associated with them
Explanation: In a directed graph, each edge has a direction associated with it, indicating the flow or relationship between vertices.
2.What type of graph allows edges to connect vertices without any specific direction?
A) Directed graph
B) Weighted graph
C) Undirected graph
D) Sparse graph
Answer: C) Undirected graph
Explanation: In an undirected graph, edges connect vertices without any direction, meaning they can be traversed in both directions.
3.Which data structure is commonly used for the representation of graphs?
A) Stack
B) Queue
C) Array
D) Adjacency list or matrix
Answer: D) Adjacency list or matrix
Explanation: Adjacency lists or matrices are commonly used to represent graphs, where vertices and their connections are stored efficiently.
4.Depth First Search (DFS) and Breadth First Search (BFS) are examples of:
A) Graph algorithms
B) Sorting algorithms
C) Searching algorithms
D) Dynamic programming algorithms
Answer: A) Graph algorithms
Explanation: DFS and BFS are algorithms used to traverse or search through graphs efficiently.
5.Which graph traversal algorithm uses a queue data structure?
A) Depth First Search (DFS)
B) Breadth First Search (BFS)
C) Dijkstra’s algorithm
D) Prim’s algorithm
Answer: B) Breadth First Search (BFS)
Explanation: BFS utilizes a queue to explore and visit all the neighbors of a vertex before moving on to the next level of vertices.
6.Kruskal’s and Prim’s algorithms are used to find:
A) Shortest path in a graph
B) Minimum spanning tree in a graph
C) Maximum flow in a graph
D) Strongly connected components in a graph
Answer: B) Minimum spanning tree in a graph
Explanation: Both Kruskal’s and Prim’s algorithms are used to find the minimum spanning tree of a graph, which is a subset of edges that connects all the vertices with the minimum possible total edge weight.
7.Dijkstra’s algorithm is used to find:
A) Shortest path in a graph
B) Minimum spanning tree in a graph
C) Strongly connected components in a graph
D) Maximum flow in a graph
Answer: A) Shortest path in a graph
Explanation: Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights.
8.Which of the following graph algorithms requires edge weights to be non-negative?
A) Dijkstra’s algorithm
B) Kruskal’s algorithm
C) Depth First Search (DFS)
D) Breadth First Search (BFS)
Answer: A) Dijkstra’s algorithm
Explanation: Dijkstra’s algorithm assumes non-negative edge weights to find the shortest path efficiently.
9.Which graph algorithm has similarities with Prim’s algorithm?
A) Kruskal’s algorithm
B) Dijkstra’s algorithm
C) Depth First Search (DFS)
D) Breadth First Search (BFS)
Answer: A) Kruskal’s algorithm
Explanation: Both Kruskal’s and Prim’s algorithms are used to find minimum spanning trees, but they have different approaches.
10.Which graph algorithm guarantees finding the shortest path from a source vertex to all other vertices?
A) Prim’s algorithm
B) Kruskal’s algorithm
C) Depth First Search (DFS)
D) Dijkstra’s algorithm
Answer: D) Dijkstra’s algorithm
Explanation: Dijkstra’s algorithm is specifically designed to find the shortest path from a source vertex to all other vertices in a graph.
11.What is the main difference between Prim’s and Kruskal’s algorithms?
A) Prim’s algorithm uses a priority queue, while Kruskal’s algorithm uses a stack.
B) Prim’s algorithm operates on directed graphs, while Kruskal’s algorithm operates on undirected graphs.
C) Prim’s algorithm grows a single tree from the chosen vertex, while Kruskal’s algorithm builds the MST by gradually adding edges.
D) Prim’s algorithm always produces the minimum spanning tree with the smallest number of edges.
Answer: C) Prim’s algorithm grows a single tree from the chosen vertex, while Kruskal’s algorithm builds the MST by gradually adding edges.
Explanation: Prim’s algorithm starts from a single vertex and grows a tree by adding the minimum weight edge at each step, while Kruskal’s algorithm adds edges based on their weight regardless of the current structure.
12.What is the time complexity of Dijkstra’s algorithm?
A) O(V)
B) O(V log V)
C) O(V^2)
D) O(V + E)
Answer: D) O(V + E)
Explanation: The time complexity of Dijkstra’s algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
13.Which graph traversal algorithm uses recursion?
A) Breadth First Search (BFS)
B) Depth First Search (DFS)
C) Prim’s algorithm
D) Dijkstra’s algorithm
Answer: B) Depth First Search (DFS)
Explanation: DFS is often implemented using recursion to explore vertices and their neighbors deeply before backtracking.
14.Which of the following is NOT an application of graphs?
A) Social network analysis
B) Shortest path finding
C) Sorting
D) Network routing
Answer: C) Sorting
Explanation: While graphs can be used to represent sorting problems indirectly, sorting itself is not a direct application of graphs.
15.In which type of graph can edges only connect vertices in one direction?
A) Undirected graph
B) Directed graph
C) Weighted graph
D) Complete graph
Answer: B) Directed graph
Explanation: Directed graphs have edges with specific directions, allowing connections to flow from one vertex to another in a defined direction.
16.Which data structure is typically used to implement Breadth First Search (BFS)?
A) Stack
B) Queue
C) Priority queue
D) Binary search tree
Answer: B) Queue
Explanation: BFS uses a queue data structure to maintain the order of vertices to visit.
17.Which graph algorithm works efficiently only for graphs with non-negative edge weights?
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Depth First Search (DFS)
D) Dijkstra’s algorithm
Answer: D) Dijkstra’s algorithm
Explanation: Dijkstra’s algorithm assumes non-negative edge weights to find the shortest path efficiently; negative weights can cause it to produce incorrect results.
18.Which graph traversal algorithm explores as far as possible along each branch before backtracking?
A) Breadth First Search (BFS)
B) Depth First Search (DFS)
C) Dijkstra’s algorithm
D) Prim’s algorithm
Answer: B) Depth First Search (DFS)
Explanation: DFS explores as far as possible along each branch before backtracking to explore other branches.
19.Which graph algorithm aims to find a subset of edges that connects all vertices with the minimum possible total edge weight?
A) Shortest path algorithm
B) Maximum flow algorithm
C) Minimum spanning tree algorithm
D) Strongly connected components algorithm
Answer: C) Minimum spanning tree algorithm
Explanation: The goal of minimum spanning tree algorithms like Kruskal’s and Prim’s is to find a subset of edges with the minimum total weight that connects all vertices in the graph.
20.Which graph algorithm is particularly useful for finding the shortest path between two vertices in a weighted graph?
A) Kruskal’s algorithm
B) Prim’s algorithm
C) Depth First Search (DFS)
D) Dijkstra’s algorithm
Answer: D) Dijkstra’s algorithm
Explanation: Dijkstra’s algorithm is designed specifically to find the shortest path between two vertices in a weighted graph, provided the edges have non-negative weights.