gsliepen/tinc — pull request #4 by licheng (2013-01-17 05:55:06+00:00)
Title: Fix the Kruskal's algorithm in generating MST.

Current implementation uses only a "visited" mark to indicate whether an edge is needed to be added into MST. This can sometimes generate incorrect result.

For example, suppose Node A has 2 connections to B and C, and the network has following edges (sorted by weight):
- C <---> D, weight 10
- A <---> B, weight 20
- A <---> C, weight 30.

C<->D & A<->B are added respectively and all of A/B/C/D are marked visited but only A<->B is marked as MST (C<->D does not associate with a connection in Node A). Then A<->C will not be added because both A&C are marked visited. The generated MST is not even connected and all broadcast packets from A to C are lost.

To fix the problem a structure of disjoint-set is added. The structure is used to decide if two nodes are already connected when adding an edge.