Kruskal's Algorithm and Spanning Trees

This video tutorial introduces Kruskal's Algorithm, a method for finding the minimum cost spanning tree in a graph. It explains the concept of a spanning tree and demonstrates the algorithm through three examples, including a basic application, a complex graph, and a table representation. The tutorial emphasizes avoiding circuits and selecting edges with the least weight to form the spanning tree.

What is the primary goal of Kruskal's Algorithm?

• To find the shortest path between two vertices

• To find the minimum cost spanning tree

• To find the maximum flow in a network

• To find the longest path in a graph

Which of the following is NOT a characteristic of a spanning tree?

• It has no circuits

• It contains circuits

• It is a connected graph

• It includes all vertices of the graph

What is the first step in Kruskal's Algorithm?

• Select the edge with the highest weight

• Select the cheapest unused edge

• Select the edge with the second highest weight

• Select any random edge

In the first example, which edge was selected first?

• Edge A, B

• Edge C, D

• Edge B, C

• Edge A, C

What is the total weight of the minimum cost spanning tree in the first example?

• 24

• 18

• 20

• 22

In the second example, which edge was NOT used due to forming a circuit?

• Edge A, B

• Edge G, H

• Edge B, F

• Edge E, F

What is the total cost of the minimum spanning tree in the second example?

• $70,000

• $60,000

• $68,000

• $65,000

In the table representation example, why is each weight given twice?

• To ensure accuracy

• To duplicate data for redundancy

• To confuse the algorithm

• To represent both directions of an edge

Which edge was not used in the table example due to forming a circuit?

• Edge A, E

• Edge B, E

• Edge C, E

• Edge D, E

What is the total weight of the minimum cost spanning tree in the table example?

• 61

• 57

• 55

• 59