Kruskal’s algorithm is a greedy algorithm for finding the minimum spanning tree (MST) of a weighted graph. It works by repeatedly adding the lightest edge to the MST, as long as doing so does not create a cycle.

Pseudocode:

1. Sort the edges of the graph in ascending order by weight.
2. Initialize a disjoint set data structure, with each vertex in its own set.
3. For each edge in the sorted list:
    * If the two vertices of the edge are in different sets:
        * Add the edge to the MST.
        * Merge the two sets.
    * If the two vertices of the edge are in the same set:
        * Ignore the edge.
4. Return the MST.

Example:

Consider the following weighted graph:

A - (5) - B
|           |
|           |
C - (3) - D

To find the MST of this graph using Kruskal’s algorithm, we would first sort the edges in ascending order by weight:

(3) C - D
(5) A - B

Then, we would initialize a disjoint set data structure with each vertex in its own set:

Set A = {A}
Set B = {B}
Set C = {C}
Set D = {D}

Next, we would iterate over the sorted list of edges, adding each edge to the MST and merging the two sets that the edge connects, as long as doing so does not create a cycle.

Step 1: We add the edge (3) C – D to the MST and merge the sets C and D:

Set A = {A}
Set B = {B}
Set CD = {C, D}

Step 2: We add the edge (5) A – B to the MST and merge the sets A and B:

Set CD = {C, D}
Set AB = {A, B}

At this point, we have added all of the edges to the MST without creating a cycle. The MST is therefore:

A - (5) - B
|           |
|           |
C - (3) - D

Prim’s Algorithm

Prim’s algorithm is another greedy algorithm for finding the MST of a weighted graph. It works by repeatedly adding the lightest edge that connects a vertex in the MST to a vertex not yet in the MST.

Pseudocode:

1. Choose a starting vertex and add it to the MST.
2. While the MST does not include all of the vertices in the graph:
    * Find the lightest edge that connects a vertex in the MST to a vertex not yet in the MST.
    * Add the edge to the MST.
    * Add the new vertex to the MST.
3. Return the MST.

Example:

Consider the same weighted graph from the previous example:

A - (5) - B
|           |
|           |
C - (3) - D

To find the MST of this graph using Prim’s algorithm, we would first choose a starting vertex, say A. We would then add A to the MST and find the lightest edge that connects A to a vertex not yet in the MST. That edge is (3) C – D, so we would add that edge to the MST.

Next, we would add the new vertex C to the MST and repeat the process. The next lightest edge that connects a vertex in the MST to a vertex not yet in the MST is (5) A – B, so we would add that edge to the MST.

At this point, we have added all of the vertices to the MST. The MST is therefore:

A - (5) - B
|           |
|           |
C - (3) - D

Comparison of Kruskal’s and Prim’s Algorithm

Both Kruskal’s and Prim’s algorithms are greedy algorithms for finding the MST of a weighted graph. They both have the same time complexity of O(E log E), where E is the number of edges in the graph. However, they have different space complexity requirements. Kruskal’s algorithm requires O(E) space to store the sorted list of edges, while Prim’s algorithm only requires O(V) space to store the priority queue of vertices.

In practice, Kruskal’s algorithm is generally faster than Prim’s algorithm for sparse graphs, while Prim’s algorithm is generally faster for dense graphs.

Applications of Kruskal’s and Prim’s Algorithm

Kruskal’s and Prim’s algorithms are