kruskals algo

Kruskal's algorithm is a greedy algorithm to find a minimum spanning tree for a weighted connected graph. It works by finding the cheapest edge that connects two different trees in the forest, and then adding that edge to the forest. This process is repeated until all of the vertices are connected in a single tree.

Here is the implementation of Kruskal's algorithm in Python:

Python

class Graph:

  def __init__(self, vertices):

    self.vertices = vertices

    self.graph = {}

    for vertex in self.vertices:

      self.graph[vertex] = []

  def

 

addEdge(self, u, v, weight):

    self.graph[u].append((v, weight))

    self.graph[v].append((u, weight))

def find(parent, i):

  if parent[i] != i:

    parent[i] = find(parent, parent[i])

  return parent[i]

def union(parent, rank, x, y):

  xRoot = find(parent, x)

  yRoot = find(parent, y)

  if rank[xRoot] < rank[yRoot]:

    parent[xRoot] = yRoot

  elif rank[xRoot] > rank[yRoot]:

    parent[yRoot] = xRoot

  else:

    parent[yRoot] = xRoot

    rank[yRoot] += 1

def

 

kruskalMST(graph):

  vertices = list(graph.keys())

  edges = []

  for u in graph:

    for v, weight in graph[u]:

      edges.append((weight, u, v))

  edges.sort()

  parent = {}

  rank = {}

  for vertex in vertices:

    parent[vertex] = vertex

    rank[vertex] = 0

  mst = []

  for weight, u, v in edges:

    if find(parent, u) != find(parent, v):

      mst.append((u, v, weight))

      union(parent, rank, u, v)

  return mst

# Example usage

graph = Graph(["A", "B", "C", "D", "E", "F"])

graph.addEdge("A", "B", 4)

graph.addEdge("A", "C", 3)

graph.addEdge("B", "C", 2)

graph.addEdge("B", "D", 5)

graph.addEdge("C", "D", 7)

graph.addEdge("C", "E", 6)

graph.addEdge("D", "E", 8)

graph.addEdge("D", "F", 2)

graph.addEdge("E", "F", 1)

mst = kruskalMST(graph.graph)

# Print the minimum spanning tree

print("Minimum Spanning Tree:")

for u, v, weight in mst:

  print(f"{u} - {v} ({weight})")

Use code with caution. Learn more

This code outputs the following:

Minimum Spanning Tree:

E - F (1)

B - C (2)

D - F (2)

A - C (3)

B - D (5)

Correctness of Kruskal's algorithm:

Kruskal's algorithm is correct because it is a greedy algorithm that always makes the locally optimal choice of adding the cheapest edge that connects two different trees in the forest. This ensures that the final spanning tree will be minimal in weight.

Here is a proof of the correctness of Kruskal's algorithm:

Let T be a minimum spanning tree of the graph G.

Let e be an edge that is not in T, but that connects two different trees in the forest formed by T.

If e were added to T, it would create a cycle.

Let C be the cycle formed by adding e to T.

Let f be the most expensive edge in C.

If we remove f from C, we are left with two trees that are still connected by e.

The weight of the resulting tree is less than or equal to the weight of T, because the weight of e is less than or equal to the weight of f.

Therefore, Kruskal's algorithm must find a minimum spanning tree.

I hope this helps! Let me know if you have any other questions.

Sources

github.com/puneet4840/Data-Structure-and-Algorithms

github.com/ManhPP/WSN

www.programiz.com/dsa/kruskal-algorithm