Name:

Kruskal's Algorithm

Description:

Function:

to find the minimum spanning tree of a graph

Time complexity:

O(m log(m))

Space complexity

O(m)

Important tips:

1. The graph can contain edges with negative length.
2. Remember to check whether the graph is connected.
3. It is a good idea to use DSU to decide connectivity, so that high efficiency can be achieved.

More information

Image