Notes from CS2040S Week 12 Lecture 1 on MSTs

cs2040s_w12_l1.md

CS2040s Week 12 Lecture 1

Notes from CS2040S Week 12 Lecture 21 on Minimum Spanning Trees

MST

• A spanning tree with minimum weight
• Covers all nodes once
• No cycles
• If you cut an MST, both pieces are MSTs
• For every cycle, max weight edge is not in the MST
• For ever cut D, the minimum weight edge that crosses the cut is in the MST

Generic Red-Blue MST

• Red rule
• Blue rule
• Greedy algorithm to color edges until no more edges can be colored

MST Algorithms

Prim's Algorithm

• Maintain set of nodes connected by blue edges
  • Initially empty with start node S = {A}
  • Repeat
    • Identify cut: {S, V-S}
    • Find minimum weight edge on cut so far
    • Add new node to S
• Maintain the edges in a Priority Queue based on the edge weight
  • Always poll the minimum weight edge
• Runtime of O(E logV)
  • For each vertex -> remove/add to queue once -> O(V logV) cost
  • For each edge -> one decreaseKey operation -> O(E logV) cost
    • If edges are stored instead of nodes, it is O(E logE)

while (PQ not empty):
	v = PQ.minimum()
	S.put(v)
	for edge e from v:
		w = node from v via e
		if (!S.get(w)):
			PQ.decreaseKey(w, e.getWeight()) // does nothing if new weight > old weight
			parent.put(w, v)

// decrease key updates the value of the node's distance to e's weight from infinity

Comparison with Dijkstra's Algorithm

Prim's

• Maintain a set of visted nodes
• Greedily grow the set of nodes by adding via the smallest edge
• Use PQ to order nodes by weight

Dijkstra's

• Maintain a set of visited nodes
• Greedily grow the set by adding neighbouring node that is closest to source
• Use PQ to order nodes by distance

Kruskal's Algorithm

• Sort edges by weight from smallest to largest
• Consider edges in ascending order
  • If both endpoints are in the same blue tree, color the edge red
  • Otherwise, color edge blue
• If an edge has been seen, then it must be part of the MST since we're looking at it in ascending order
• Uses Union Find
  • Connect two nodes if they are in the same blue tree
• Runtime of O(E logV)
  • Sorting causes O(E log E) = O(E logV) -> E <= V^2
  • For each edge
    • Find: O(alpha(n)) or O(logV)
    • Union O(alpha(n) or O(logV)

sorted = sort(edges)
mstEdges = new array of edges
union uf = new unionfind(nodes) // to check for cycles/connected components

for i from 0 to sorted.length:
	e = sorted[i]
	v = e.one() // get endpoints
	w = e.two()
	if (!uf.find(v, w)):
		mstEdges.add(e)
		uf.union(v, w)

Boruvka's Algorithm

• Add all edges that are "obviously" in the MST – follow MST properties

  • Minimum adjacent edge to all nodes needs to be in
    • at least n/2 edges
  • Look at connceted components
    • at most n/2 connected components
  • Repeast for every CC and add minimum outgoing edge

• For each node store a component identifier O(V)

• For each step O(V + E)

  • For each CC, search for minimum weight edge O(V + E)
    • Use DFS/BFS to check if edge connetcs two components
    • Remember minimum cost edge connected to each component
  • Add selected edges
  • merge CCs
    • Compute new component IDs, update IDs, mark arred edges

• If all nodes add their own minimum edge, there cannot be cycles

• Each component adds one edge

• Some choose same edge

• Each edge is chosen by at most two different components

• At most O(logV) Boruvka steps

• Runtime of O((E+V) logV) = O(E log V)

• Can be parallellised

  • Each component can search for its own minimum edge
  • Many edges found in parallel
  • Merging is the main bottleneck

MST Variants

• What if all the weights are the same?
  • Runtime of O(E) since we don't need to sort
  • Use DFS/BFS to find a MST since any ST will be a MST
    • Contains V-1 edges
• If the edge weights are 2, the cost is 2(V-1)
• If all edges have weights from {1...10}
  • Use an array of size 10 to sort
    • Each index has a linked list
    • Put each edge in the linked list

Directed MST

• Edges have directions

• For a DAG, for every node except root, add minimum weight incoming edge

  • Each edge is chosen once
  • No cycles
    • V nodes, V-1 edges, No cycles
    • Every node has to have at least one incoming edge in the MST, so this is the MST

• Runtime of O(E) for DAG

• In general directed graph, it's difficult

• Min/Max ST doesn't change if a constant k is added to all weights

• Min/Max ST doesn't change with negative weights

  • Only relative weights of edges matter

Maximum Spanning Tree

• Negate the weights by * -1
• Run Kruskal/Prim in reverse order

Steiner Tree Problem

• MST of a subgraph of a larger graph – Steiner Graph
• Has the required nodes and optional Steiner nodes
  • Just use the subgraph
  • Use other nodes
• It's best to consider using Steiner nodes

SteinerMST Algorithm

• For every pair of required verices (v, w), calculate the shortest path from v and w
  • Use Dijkstra
• Construct new graph on required nodes
• Run MST on new graph
• Map new edges back to original graph

Does not guarantee optimal Steiner tree (just an approximation)