9UNION-FIND
We used the adjacency list data structure—and algorithms on it—to solve graph problems in Chapters 5 and 6. That’s an efficient data structure that works no matter the graph problem. However, if we constrain the types of problems we want to solve, we can design an even more efficient data structure. Constrain the problems just a little, and we likely wouldn’t be able to do any better than an adjacency list. Constrain them too much, and few people would use our data structure because it would be unlikely to solve problems that they cared about solving. Constrain the problems just right and you have the union-find data structure, the ...
Get Algorithmic Thinking, 2nd Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
