Intermediate Graph Theory: Exploring Minimum Spanning Tree Algorithms
Assess your understanding of Minimum Spanning Tree algorithms in graph theory.
Questions in this quiz
12 questions on Intermediate Graph Theory: Exploring Minimum Spanning Tree Algorithms. Work through them here, then start the quiz to answer them and see your score.
1.What is the primary purpose of a Minimum Spanning Tree (MST) in a graph?
- ATo find the shortest path between two nodes
- BTo connect all nodes with the minimum total edge weight
- CTo connect all nodes with the maximum total edge weight
- DTo find the longest path in a graph
2.Which of the following algorithms is NOT used to find a Minimum Spanning Tree?
- AKruskal's Algorithm
- BPrim's Algorithm
- CBorůvka's Algorithm
- DDijkstra's Algorithm
3.In Kruskal's algorithm, what data structure is commonly used to detect cycles?
- AStack
- BPriority Queue
- CQueue
- DUnion-Find
4.What is the time complexity of Prim's algorithm using a binary heap?
- AO(E + V log V)
- BO(E log V)
- CO(V log E)
- DO(V^2)
5.Which condition must be satisfied for a graph to have a unique Minimum Spanning Tree?
- AAll edge weights are distinct
- BThe graph is a bipartite graph
- CThe graph is a directed graph
- DThe graph is a complete graph
6.In Prim's algorithm, how is the next edge chosen to be added to the MST?
- AThe edge with the maximum weight
- BThe edge that connects the most vertices
- CThe edge that forms a cycle
- DThe edge with the minimum weight that connects a new vertex
7.Which of the following statements is true about Kruskal's algorithm?
- AIt always starts with the smallest edge in the graph.
- BIt can handle disconnected graphs by finding MSTs for each component.
- CIt requires the graph to be connected initially.
- DIt starts with a single vertex and grows the MST one edge at a time.
8.What is the primary difference between Prim's and Kruskal's algorithms?
- APrim's algorithm is faster than Kruskal's in all cases.
- BPrim's algorithm is greedy, while Kruskal's is not.
- CPrim's algorithm works on directed graphs, Kruskal's on undirected.
- DPrim's algorithm grows a single tree, Kruskal's considers all edges.
9.Which data structure can optimize Prim's algorithm to run in O(E + V log V) time?
- AAdjacency List
- BFibonacci Heap
- CBinary Heap
- DAdjacency Matrix
10.What is a key characteristic of Borůvka's algorithm?
- AIt uses a priority queue to select edges.
- BIt requires sorting all edges before execution.
- CIt adds all edges of minimum weight simultaneously.
- DIt starts with the heaviest edge.
11.Which algorithm is more efficient for dense graphs?
- APrim's Algorithm with a priority queue
- BKruskal's Algorithm
- CPrim's Algorithm with an adjacency matrix
- DBorůvka's Algorithm
12.What happens if you run Kruskal's algorithm on a graph with negative edge weights?
- AIt will find the MST correctly.
- BIt will fail to find an MST.
- CIt will ignore negative edges.
- DIt will only work if the graph is connected.