Algorithms Graph Algorithms & Traversal

Question 1

Which graph traversal algorithm uses a queue as its primary data structure?

Accepted Answer

Breadth-First Search

Answer

Depth-First Search

Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Question 2

What does Dijkstra's algorithm compute for a weighted graph?

Accepted Answer

Shortest path from a single source

Answer

Minimum spanning tree

Answer

All-pairs shortest paths

Answer

Topological order

Question 3

Which algorithm can detect negative-weight cycles in a graph?

Accepted Answer

Bellman-Ford Algorithm

Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Answer

Kruskal's Algorithm

Question 4

What is the time complexity of BFS on a graph with V vertices and E edges?

Accepted Answer

O(V + E)

Answer

O(V²)

Answer

O(E log V)

Answer

O(V log V)

Question 5

Which algorithm is used to find the Minimum Spanning Tree of a graph by adding the cheapest edge that doesn't form a cycle?

Accepted Answer

Kruskal's Algorithm

Answer

Dijkstra's Algorithm

Answer

Prim's Algorithm

Answer

Bellman-Ford Algorithm

Question 6

In a directed graph, what is a topological sort?

Accepted Answer

Ordering vertices so every edge points from earlier to later

Answer

Sorting vertices by degree

Answer

Finding the shortest path

Answer

Identifying strongly connected components