DSA + System Design - 16

Which of the following algorithms is most efficient to find the shortest path in a weighted graph with non-negative weights?

• Breadth-First Search (BFS)

• Depth-First Search (DFS)

• Dijkstra's Algorithm

• Bellmanford

What is the time complexity of DFS and BFS for traversal of a graph?

• O(V + E)

• O(V^2)

• O(E^2)

• O(V)

Which data structure is used in the implementation of Prim’s Algorithm for finding the Minimum Spanning Tree?

• Stack

• Queue

• Min-Heap (Priority Queue)

• Hash Table

In a connected undirected graph, what is the Maximum number of edges in a spanning tree?

• V

• V - 1

• E

• E - 1

In the context of graphs, what does the term "bipartite" mean?

• The graph is connected and acyclic

• The graph can be colored with two colors without any two adjacent vertices having the same color

• The graph contains a cycle

• The graph is weighted

Which of the following algorithms is used to find all pairs shortest paths in a graph?

• Bellman-Ford Algorithm

• Floyd-Warshall Algorithm

• Prim’s Algorithm

• Dijkstra’s Algorithm

Which algorithm can handle negative weights and negative cycles in a graph while finding single source shortest path?

• Dijkstra’s Algorithm

• Bellman-Ford Algorithm

• Prim’s Algorithm

• Floyd-Warshall Algorithm

In a complete graph with N vertices, how many edges are there?

• N - 1

• N(N - 1) / 2

• N^2

• 2N - 1

Which of the following algorithms uses the concept of union and find to detect a cycle in an undirected graph?

• Dijkstra’s Algorithm

• Bellman-Ford Algorithm

• Kruskal’s Algorithm

• Floyd-Warshall Algorithm

Which Data Structure is used by DFS and BFS ?

• Tree, Graph

• Stack, Queue

• Array, Linkedlist

• None of these