Kruskels

Algorithm

English

Method 1

1. Started with the lowest weighted edge

2. Select any next lowest weighted edge (does not have to be connected) such that does not create a cycle.

3. Repeat process ii. Stop once each node has become connected with an edge.

Method 2

1. Sorted edges in descending order into list A.

2. Select edge from list A such that it doesn't create a disconnected graph.

3. See 2.

Less English

1. Note union by size, or union by height.

2. List all of the nodes into an array, and initialize all of their size/height to -1.

3. Begin to use union operations, starting with the lowest weighted node and progressing in ascending order.

   1. (See union operations).

   2. Once a union has been made. Update the size or the height of the new root. Note that the root will always have a negative value, and the other unioned element or tree will point to the index the root element is in.

   3. Reject union operations if the nodes (parameters of the union operation) already are unioned (e.g. exist in the same tree)

   4. Even though the union operations is ignored, note that with path compression, there is potential for node element to compress. Hence changing the pointer indexes.

   5. Stop once all the node elements are unioned (e.g. exist in the same tree).

4. There will always be a maximum of two update operations per union. 1) Updating the new size of the root, and 2) updating the pointer to root index.

Time Complexity

• O(ElogE)

• O(ElogV) with smart unions.