Minimum Spanning Tree
Given a connected and undirected graph, find the minimum spanning tree of the graph. The minimum spanning tree is a subgraph that connects all the vertices together while minimizing the total edge cost.
Constraints:
- The graph is connected and undirected
- The graph has no self-loops or multiple edges between any two vertices
- The graph has a non-negative edge weight
Examples:
Input: [[0, 0, 2], [0, 1, 3], [1, 2, 1], [2, 0, 1]]
Output: [[0, 1, 1], [1, 2, 1], [2, 0, 1]]
Explanation: The minimum spanning tree has edges (0, 1) with weight 1, (1, 2) with weight 1, and (2, 0) with weight 1, with a total weight of 3.
Solutions
Kruskal's Algorithm
Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree of a graph. It works by sorting the edges of the graph by weight and then iterating over the sorted edges. For each edge, it checks if the two vertices of the edge are in the same connected component. If they are not, it adds the edge to the result and merges the two components.
def find_minimum_spanning_tree(edges):
parent = {}
rank = {}
result = []
# Initialize the parent and rank arrays
for i in range(len(edges)):
parent[i] = i
rank[i] = 0
# Sort the edges by weight
edges.sort(key=lambda x:
x[2])
# Iterate over the sorted edges and add them to the result if they do not form a cycle
for u, v, weight in edges:
if find(parent, u) != find(parent, v):
result.append([u, v, weight])
union(parent, rank, u, v)
return result
def find(parent, i):
if parent[i] == i:
return i
return find(parent, parent[i])
def union(parent, rank, u, v):
root_u = find(parent, u)
root_v = find(parent, v)
if rank[root_u] < rank[root_v]:
parent[root_u] = root_v
elif rank[root_u] > rank[root_v]:
parent[root_v] = root_u
else:
parent[root_v] = root_u
rank[root_u] += 1Follow-up:
How would you modify the algorithm to find the maximum spanning tree of a graph?
