disjoint set union(dsu)

PPTX 27 pages 1.1 MB Free download

27 pages

FaylHub.uz

Download via Telegram

Size 1.1 MB

File type PPTX

Pages 27

Updated Dec 2025

Page preview (5 pages)

Scroll down 👇

1 / 27

disjoint set union (dsu) disjoint set union (dsu) algorithms and data structures course disjoint set union (dsu) algorithms and data structures course we are given several elements, each of which is a separate set. a disjoint set union (dsu) have a following operation over given elements: add element to a set. combine any two sets. tell in which set a specific element is. disjoint set union (dsu) algorithms and data structures course thus the basic interface of this data structure consists of only three operations: - creates a new set consisting of the new element . - merges the two specified sets (the set in which the element is located, and the set in which the element is located) - returns the representative (also called leader) of the set that contains the element . this representative is an element of its corresponding set. it is selected in each set by …

2 / 27

example algorithms and data structures course then we combine the set containing the element 5 and the set containing the element 4. 1 2 3 4 5 6 disjoint set union (dsu) example algorithms and data structures course and in the last step we can the sets containing the elements 1 and 3 are merged. 1 2 3 4 5 6 disjoint set union (dsu) example algorithms and data structures course for the implementation this means that we will have to maintain an array parent that stores a reference to its immediate ancestor in the tree. 1 2 3 4 5 6 disjoint set union (dsu) naive implementation algorithms and data structures course we can already describe the first implementation of the disjoint set union data structure. it will be pretty inefficient at first, but later we can improve it using two optimizations, so that it will take nearly constant …

3 / 27

e identical, that we have nothing to do, the sets are already merged. otherwise, we can simply specify that one of the representatives is the parent of the other representative - thereby combining the two trees. for example, will change our array in the following way: element 0 1 2 3 4 5 6 7 8 parent 0 1 5 3 3 5 6 7 8 disjoint set union (dsu) algorithms and data structures course to combine two sets (operation ), we first find the representative of the set in which is located, and the representative of the set in which is located. if the representatives are identical, that we have nothing to do, the sets are already merged. otherwise, we can simply specify that one of the representatives is the parent of the other representative - thereby combining the two trees. for example, will change our array in the …

4 / 27

n (dsu) algorithms and data structures course however this implementation is inefficient. it is easy to construct an example, so that the trees degenerate into long chains. in that case each call can take time. this is far away from the complexity that we want to have (nearly constant time). therefore we will consider two optimizations that will allow to significantly accelerate the work. disjoint set union (dsu) path compression optimization algorithms and data structures course this optimization is designed for speeding up . if we call for some vertex , we actually find the representative for all vertices that we visit on the path between and the actual representative . the trick is to make the paths for all those nodes shorter, by setting the parent of each visited vertex directly to . disjoint set union (dsu) path compression optimization algorithms and data structures course you can see the …

5 / 27

mization we will avoid this by choosing very carefully which tree gets attached. there are many possible heuristics that can be used. most popular are the following two approaches: in the first approach we use the size of the trees as rank, and in the second one we use the depth of the tree (more precisely, the upper bound on the tree depth, because the depth will get smaller when applying path compression). in both approaches the essence of the optimization is the same: we attach the tree with the lower rank to the one with the bigger rank. disjoint set union (dsu) union by size / rank algorithms and data structures course here is the implementation of union by size: disjoint set union (dsu) union by size / rank algorithms and data structures course and here is the implementation of union by rank based on the depth of the …

Want to read more?

Download all 27 pages for free via Telegram.

Download full file

About "disjoint set union(dsu)"

disjoint set union (dsu) disjoint set union (dsu) algorithms and data structures course disjoint set union (dsu) algorithms and data structures course we are given several elements, each of which is a separate set. a disjoint set union (dsu) have a following operation over given elements: add element to a set. combine any two sets. tell in which set a specific element is. disjoint set union (dsu) algorithms and data structures course thus the basic interface of this data structure consists of only three operations: - creates a new set consisting of the new element . - merges the two specified sets (the set in which the element is located, and the set in which the element is located) - …

This file contains 27 pages in PPTX format (1.1 MB). To download "disjoint set union(dsu)", click the Telegram button on the left.

Tags: disjoint set union(dsu) PPTX 27 pages Free download Telegram