# Graph

Category: /template

# Template

Dijkstra’s algorithm is used to compute the minimal distance from a node to all the other nodes in a weighted graph.

Kruskal’s and Prim’s algorithm are used to compute the minimum spanning tree.

## Kruskal MST algo:

Kruskal in wikipedia

``````
# create MST over a created graph
q = []
for i in range(len(points)):
for j in range(i+1, len(points)):
dis = abs(points[i]-points[j]) + abs(points[i] - points[j])
q.append((dis, i, j))

# MST search algorithm Kruskal
def find(x):
""" find connected parent """
if (x != parent[x]):
parent[x] = find(parent[x])
return parent[x]

def union(x, y):
""" merge two sets to the bigger one"""
if size[x] > size[y]:
size[x] += size[y]
parent[y] = x
else:
size[y] += size[x]
parent[x] = y

n = len(points)
parent = [i for i in range(n+1)]  # [0, n]
size = [1 for _ in range(n+1)]    # [0, n]
q.sort()  # sort edges
res = 0
count = 0
for w, u, v in q:
rA, rB = find(u), find(v)
if rA == rB:
continue
union(rA, rB)
res += w
# Optimize so that we don't traverse all edges
count += 1
if count == n:
return res
return res
``````

## Prim’s MST algo

``````	# MST search algorithm Prim
G = collections.defaultdict(list)
for i in range(len(points)):
for j in range(i+1, len(points)):
dis = abs(points[i]-points[j]) + abs(points[i] - points[j])
G[i].append((dis, j))
G[j].append((dis, i))

visited = {0}
pq = G
heapq.heapify(pq)
res = 0
while len(visited) < len(points) and pq:
w, v = heapq.heappop(pq)
if v not in visited:
res += w