Sunday, April 28, 2019

Algorithms: Union-Find in C#

Union-Find Algorithm: Imagine if you have 100 computers in a room not networked to one another. You could use a Union(computer1, computer2) method to join 2 computers together in a network. From there, you could continue joining computers together randomly and you would want to have a method that returns a bool called Connected(computer1, computer2) that determines if they are already connected, so you don't have to do the work if they're already in the same network. Now, if we wanted to be a little more efficient, we could setup the connections to be in a tree format. Each computer will reference it's parent's number as an ID. The root computers will reference themselves as their ID, so you can check for that to tell if a computer is a root of a tree. Lastly, we could have balanced trees to ensure we have no extremely tall trees. A component is how many groups of computers that we have a component could be 1 computer by itself, or it could be all of the computers in a component if every computer has been networked together at some point with the Union() method. We should keep track of the size of each component and how many total components we have in our data set.