Introduction to Graph Algorithms: Shortest Path and Minimum Spanning Tree
A beginner-level quiz on understanding shortest path and minimum spanning tree algorithms in graph theory.
Questions in this quiz
15 questions on Introduction to Graph Algorithms: Shortest Path and Minimum Spanning Tree. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary goal of Dijkstra's algorithm?
- ATo find the shortest path from a single source to all vertices
- BTo find the minimum spanning tree of a graph
- CTo detect cycles in a graph
- DTo sort the vertices of a graph
2.Which of the following algorithms is used to find a minimum spanning tree?
- AKruskal's algorithm
- BDijkstra's algorithm
- CFloyd-Warshall algorithm
- DBellman-Ford algorithm
3.In a graph with negative edge weights, which algorithm can be used to find the shortest path?
- ADijkstra's algorithm
- BBellman-Ford algorithm
- CKruskal's algorithm
- DPrim's algorithm
4.What is the time complexity of Dijkstra's algorithm using a priority queue?
- AO(E log V)
- BO(V^2)
- CO(E^2)
- DO(V log V)
5.Which data structure is commonly used in Prim's algorithm to select the minimum weight edge?
- AStack
- BHash Table
- CQueue
- DPriority Queue
6.What is the main difference between Prim's and Kruskal's algorithms?
- APrim's works on directed graphs, Kruskal's on undirected
- BPrim's is faster than Kruskal's
- CPrim's uses a stack, Kruskal's uses a queue
- DPrim's grows a single tree, Kruskal's grows a forest
7.Which algorithm can be used to detect negative weight cycles in a graph?
- AKruskal's algorithm
- BPrim's algorithm
- CBellman-Ford algorithm
- DDijkstra's algorithm
8.What is the purpose of a minimum spanning tree?
- ATo find the shortest path between two vertices
- BTo connect all vertices with the maximum total edge weight
- CTo detect cycles in a graph
- DTo connect all vertices with the minimum total edge weight
9.Which of the following is true about Dijkstra's algorithm?
- AIt is a greedy algorithm
- BIt works with graphs with negative weights
- CIt finds the longest path in a graph
- DIt uses a stack to find the shortest path
10.In Kruskal's algorithm, what is the first step?
- ASort all edges in non-decreasing order of their weight
- BFind the shortest path
- CSelect a random vertex
- DInitialize a priority queue
11.What is the time complexity of Kruskal's algorithm?
- AO(E log E)
- BO(V log V)
- CO(E log V)
- DO(V^2)
12.Which algorithm is more suitable for dense graphs when finding a minimum spanning tree?
- ABellman-Ford algorithm
- BDijkstra's algorithm
- CKruskal's algorithm
- DPrim's algorithm
13.What is a key characteristic of a spanning tree?
- AIt is a directed graph
- BIt contains cycles
- CIt has the maximum number of edges
- DIt includes all vertices of the graph
14.Which algorithm uses a union-find data structure to detect cycles?
- APrim's algorithm
- BDijkstra's algorithm
- CFloyd-Warshall algorithm
- DKruskal's algorithm
15.What is the primary application of the Floyd-Warshall algorithm?
- ASorting vertices of a graph
- BDetecting cycles in a graph
- CFinding the shortest path between all pairs of vertices
- DFinding the minimum spanning tree