Overview
Week 12: Disjoint Sets; Intro to Graphs; Topological Sort
This week, we鈥檒l complete an implementation of the dynamic equivalence problem that comes very close to linear time for find and union; then we鈥檒l have a brief introduction to graphs; and we鈥檒l wrap up the week with our first graph algorithm: topological sort
Learning Objectives
By the end of this module, you will be able to:
- Understand how weighted union and path compression work, and how combined these give us a good implementation to solve the dynamic equivalence problem,
- Describe the fundamental components of graphs and how trees are a special case of graphs,
- Explain the difference between directed and undirected graphs, between cyclic and acyclic graphs, and between connected and disconnected graphs, and
- Implement your own version of topological sort in C++.
To achieve this module鈥檚 objectives, please watch the introductory video (above), and complete the following:
- Disjoint Sets (Dynamic Equivalence Problem),
- Introduction to Graphs, and
- Topological Sort.
- Textbook, pp. 325; 355-359 (Chapter 13, Basic Network Algorithms)
Copyright 漏 2023鈥�2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.