Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc — Part 2 MCQs with Explanations

It remains O(V2). is the correct answer to “How is the time complexity of BFS affected when the graph is represented using an adjacency matrix”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

A priority queue or min-heap to extract the minimum distance. is the correct answer to “Which of the following properties is essential for the efficient implementation of Dijkstra's algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Prim's Algorithm or Kruskal's Algorithm is the correct answer to “In a graph with weights, which algorithm helps in constructing a Minimum Spanning Tree (MST)”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Both BFS and DFS is the correct answer to “Which traversal algorithm can be used to check if a graph is bipartite”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

It remains connected even after removing any single vertex. is the correct answer to “What is a characteristic feature of a Biconnected Graph”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

d-ary heap is the correct answer to “Prim's algorithm can be efficiently implemented using . . . . . . . . for graphs with greater density.”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Min priority queue is the correct answer to “Which of the following is the most commonly used data structure for implementing Dijkstra's Algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

O(V + E) is the correct answer to “Time Complexity of DFS is? (V - number of vertices, E - number of edges)”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Peter Ingerman is the correct answer to “Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

FIFO branch and bound is the correct answer to “Which of the following branch and bound strategy leads to breadth first search”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

priority queue is the correct answer to “Which data structure is most suitable for implementing best first branch and bound strategy”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

False is the correct answer to “The time taken to compute the transitive closure of a graph is Theta(n 2 ).”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Equivalent to number of indegree of the node is the correct answer to “In BFS, how many times a node is visited”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Graph M has 3 distinct minimum spanning trees, each of cost 2 is the correct answer to “Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true? \[{\text{M}} = \left[ {\begin{array}{*{20}{c}} 0&1&1 \\ 1&0&1 \\ 1&1&0 \end{array}} \right]\]”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Highest cost branch and bound is the correct answer to “Which of the following is not a branch and bound strategy to generate branches”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

dij(k)=min(dij(k-1), dik(k-1) + dkj(k-1)) is the correct answer to “Complete the program. n=rows[W] D(0)=W for k=1 to n do for i=1 to n do for j=1 to n do ___________ return D(n)”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Dynamic Programming is the correct answer to “What approach is being followed in Floyd Warshall Algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Relaxation is the correct answer to “What is the basic principle behind Bellmann Ford Algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Bellman-Ford algorithm is the correct answer to “Which of the following is not the algorithm to find the minimum spanning tree of the given graph”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Single source shortest path is the correct answer to “Bellmann ford algorithm provides solution for . . . . . . . . problems.”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

All pair shortest path problems is the correct answer to “Floyd Warshall's Algorithm is used for solving . . . . . . . .”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

B* BFS is the correct answer to “Which algorithm is used to find the least cost path from source node to destination node”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

When the graph is a Linked List is the correct answer to “When the Breadth First Search of a graph is unique”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

queue is the correct answer to “Which data structure is used for implementing a FIFO branch and bound strategy”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Alfonso Shimbe is the correct answer to “Bellmann Ford algorithm was first proposed by . . . . . . . .”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Pre-order Traversal is the correct answer to “Depth First Search is equivalent to which of the traversal in the Binary Trees”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

DFS is equivalent to post order traversal in trees is the correct answer to “Choose the incorrect statement about DFS and BFS from the following”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

backtracking is the correct answer to “Which of the following can traverse the state space tree only in DFS manner”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

O(VE) is the correct answer to “What is the running time of Bellmann Ford Algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Graphs having negative weight function is the correct answer to “Dijkstra's Algorithm cannot be applied on . . . . . . . .”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

True is the correct answer to “Dijikstra's Algorithm is more efficient than Bellmann Ford Algorithm.”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Total number of edges is the correct answer to “The maximum number of times the decrease key operation performed in Dijkstra's algorithm will be equal to . . . . . . . .”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

tij(k) = tij(k-1) OR (tik(k-1) AND tkj(k-1)) is the correct answer to “What is the formula to compute the transitive closure of a graph”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

The total weight of the graph is negative is the correct answer to “A graph is said to have a negative weight cycle when”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

When the graph is a Linked List is the correct answer to “When the Depth First Search of a graph is unique”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

V-1 is the correct answer to “How many times the for loop in the Bellmann Ford Algorithm gets executed”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

3 is the correct answer to “How many priority queue operations are involved in Dijkstra's Algorithm”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

A minimum spanning tree is the correct answer to “The travelling salesman problem can be solved using . . . . . . . .”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

True is the correct answer to “Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not.”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.

Path Finding is the correct answer to “Which of the following is not an application of Breadth First Search”. This question is standard in competitive examination syllabi for Graph Algorithms _Dfs_ Bfs_ Dijkstras_ Etc.