# Kruskal's Algorithm

This is more of an addendum to Travelling Salesperson. I quickly made a solution to Minimum Spanning Tree problem. This algorithm runs in $$O(\alpha(E)E\log(E))$$ time. This is the Inverse Ackerman function $$\alpha$$, and it grows incredibly slow, $$\alpha (2^{2^{2^{65533}}} - 3) = 4$$. So the analysis of this algorithm would basically be $$O(E\log(E))$$, however our set-up is always a connected graph, so we can just denote it as $$E=n(n-1)/2$$, which is ~$$n^2$$. And for when $$n=|V|$$, our algorithm runs in $$O(\alpha(n^2)n^2 2\log(n))$$ which is $$O(n^2\log(n))$$. For a more detailed analysis, check Wikipedia’s for a simple to follow one here. I wanted to thank William Edwards, he posed a problem in the USC Codeathon this Spring, and it was the disjoint set data structure. It is brilliantly simple, an incredibly weird run time $$O(\alpha(n))$$, and otherwise cool algorithm. It is implemented in a not very forward facing way down below.

Also to show how fast this algorithm is, here’s 100 nodes, which would be practically unsolvable in the Travelling Salesperson Problem. ## Source Code

# Copyright 2019 Justin Baum
# Kruskals Algorithm
# kruskals-algo.py

import networkx as nx
import matplotlib.pyplot as plt
import random
#import networkutils as nu

"""
1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree
"""

def kruskals(matrix):
m = len(matrix)
E = [[i, j, matrix[i][j]] for i in range(m) for j in range(i+1,m)]
E.sort(key = lambda x: x)
walk = []
dj = list(range(m))
while len(walk) <= m - 2:
leg = E
E = E[1:]
if find(leg,dj) != find(leg, dj):
union(leg,leg,dj)
walk.append(leg)
return walk

### Disjoint Set

def find(i, dj):
while dj[i] != i:
i = dj[i]
return i

def union(i, j, dj):
a = find(i, dj)
b = find(j, dj)
dj[a] = b

def showGraph(V, matrix, walk):
X = nx.Graph()
plt.close()
E = list(map(lambda x: x[:2], walk))
nx.draw(X, V, with_labels=True)
plt.savefig('fig.png')

## Utils
def gennodes(n, size = 200):
graph = {}
for i in range(n):
x = random.randint(0, size)
y = random.randint(0,size)
graph[i] = (x,y)
return graph

def makematrix(V):
m = len(V)
matrix = [[0 for i in range(m)] for j in range(m)]
for node in V:
for neighbor in V:
point1 = V[node]
point2 = V[neighbor]
matrix[node][neighbor] = int(dist(point1, point2)**0.5)
return matrix

def dist(point1, point2):
return (point1 - point2)**2 + (point1 - point2)**2

## Run code

V = gennodes(10)
matrix = makematrix(V)

showGraph(V, matrix, kruskals(matrix))


Written on April 16, 2019 15:50 UTC-4