Overview

Week 14: Minimum Spanning Trees; Prim鈥檚 Algorithm and Kruskal鈥檚 Algorithm

This week we鈥檙e going to learn how to solve the following problems:

• Given a weighted, undirected graph, find the minimum weight tree that 鈥渟pans鈥� all nodes in the graph.

Learning Objectives

By the end of this module, you will be able to:

• Find the minimum spanning tree of an arbitrary connected, weighted undirected graph.
• Understand how to apply min heap and disjoint set find and union in implementing an algorithm for finding the minimum weight spanning tree of a graph.

To achieve this module鈥檚 objectives, please watch the introductory video (above), and complete the following:

• Minimum Spanning Trees; Prim鈥檚 algorithm and Kruskal鈥檚 algorithm
• Textbook, pp. 337-339

Review earlier material

In preparation for the final exam, you should review material from prior weeks. Exam will be comprehensive.

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.