Minimum Spanning Tree

Minimum Spanning Tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Kruskal’s Algorithm

minimumCost(n: int, connections: List[List[int]]) → int

Find the minimum cost to connect all the cities. Kruskal’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph, using Union-Find data structure

Time complexity: \(O(E \log E)\), where E is the number of edges in the graph

Space complexity: \(O(E)\)

Return type:

int

Prim’s Algorithm

Coming soon