Core Graph Algorithms Pseudocode Reference

Core Graph Algorithms Pseudocode

Kruskal's Algorithm for MST

def Kruskal(V, E):

1. Sort E by increasing weight.
2. For each vertex v in V: create a tree for each v.

MST = {}

For i from 1 to |E|:

1. (u, v) ← lightest edge in E.
2. If u and v are not in the same tree:

• MST.add((u,v))
• Merge u and v trees.

Return MST.

Huffman Tree Construction

BuildHuffman(characters[1..n], frequencies[1..n]):

• Create nodes for each character.
• For i ← 1 to n: create a min-heap Q with each node frequency as a key.

While(length(Q) > 1):

1. x = pop minimum value from Q.
2. y = pop minimum value from Q.
3. Create new node z.
4. z.key = x.key + y.key
5. z.leftChild = x
6. z.rightChild = y
7. Insert z into Q.

Return the root value from Q.

Topological Sort

topological_sort(G):

Stack = []

While (unvisited Nodes):

helper_toposort(currentNode in G):

• Mark currentNode as visited.
• For node in currentNode.neighbours:
  • If (node is not already visited): helper_toposort(node).
• Stack.insert(currentNode).

Return Result in reverse order.

Dijkstra's Shortest Path Algorithm

def Dijkstra(G, s):

1. # Add nodes to min-priority queue Q with initial distance infinity.
2. For v in V: Enqueue(Q, v, 'infinity').
3. # In Q, make source priority = 0.
4. DecreaseKey(Q, source, 0).

visited = []

While(length(Q) > 0):

1. currentNode = Dequeue(Q) # Pick and delete the min distance node.
2. visited.append(currentNode).
3. For v in currentNode.neighbours:

• If (v not in visited):
  • dist_V = min{dist_V, weight(currentNode, v) + dist_currentNode}.
  • DecreaseKey(Q, v, dist_V).

Prim's Algorithm for MST

def prims(G):

1. s ← pick a source vertex from V.
2. For v in V: # v: current vertex; V: all the vertices in G.

• dist[v] = infinity
• prev[v] = Empty

# Initialize source.

• dist[s] = 0
• prev[s] = Empty/None

# Update neighbouring nodes of s. For node in s.neighbours:

• dist[node] = weight of (s, node)
• prev[node] = s

While(length(visited) < len(V)):

• CurrentNode = unvisited vertex v with smallest dist[v].
• MST.add((prevNode, CurrentNode)).
• For node in CurrentNode.neighbours:
  • dist[node] = min(w(CurrentNode, node), dist[node]).
  • If dist[node] updated: prev[node] = CurrentNode.
• visited.add(CurrentNode).

Return MST.