## Weighted Graph Algorithms

#### Andy Novocin

## Problem of the day

### Oops, sorry.

## Math Problem of day

### (Nice version) Given the sequence 3, 2, 1, 3, 10, 23 predict the next term.

### (Hard version) Given the sequence 2, 1, 3, 10, 23 predict the next term.

### How do you generalize?

## Strongly connected components

### In directed graphs, can detect if connected by traversal and again by traversal of the reverse graph.

### To spit out the components is a bit trickier.

## Concept of algo

### Any cycle must be in a strongly connected component (SCC)

### Collapse the cycles into one 'vertex'

### CROSS edges from unlabeled components into old components also create a cycle.

### Repeat until no cycles.

## SCC Algo

## ICUP find SCC

## `<weighted-graphs>`

### First we had trees

### Then graphs

### Now weighted graphs

### It's all about the benjamins

## CheapCircuits`R`Us

## Minimum Spanning Trees

### You have to connect a set of vertices.

### Each possible edge has a cost (length of wire, travel time, political capital spent, etc)

### Make the connections at the cheapest cost

## Louis XIV (Political cost)

## BFS and DFS

### Both create a tree out of a graph.

### How many edges are in those trees?

### If all edges have the same cost (e.g. 1) then any spanning tree is minimal.

## Key concepts to spot

### Greedy algorithms sometimes work

### Graph cuts are useful

### Trees don't create much wiggle room.

## Generic MST

```
A = []
while !G.is_spanned_by(A):
(u,v) = G.find_safe_edge(A)
A.addEdge((u,v))
return A
```

#### A is "safe" if it is a subset of some MST

## Graph Cuts

### For \(G = (V, E)\) then any two set partition of \(V\) is called a cut: \( (S, V-S) \).

### A cut respects \(A \subset E\) if no edge in \(A\) crosses the cut (has an end in \(S\) and an end in \(V-S\)).

## A graph cut

## A safeness condition

### For \(A \subseteq E\) and \(A\) "safe", let \((S, V-S)\) be any cut which respects \(A\) and let \( (u,v) \in E\) be a minimal-cost edge crossing \( (S, V-S)\). Then \(A \cup (u,v) \) is safe.

## ICUP Find MST (Generic)

## Quasi-proof of safeness condition

### Let \(T\) be an MST containing \(A\) but not \( (u,v)\).

### There must be a path from \( u\) to \(v\) in \(T\) and it must contain an edge crossing \(S\) and \(V-S\), call that edge \((x, y)\).

### The weight, \( w(x,y) \geq w(u,v) \), and \(T - (x,y) + (u,v)\) is also a spanning tree with cost no larger than \(T\).

## Prim's Algorithm

### Is a special case of the generic algorithm where the cut is just:

### Vertices collected so far as \(S\) and the other vertices (as \(V-S\)).

### The edges in \(A\) always form a single tree.

## Greedy?

### This approach is greedy because each new edge is the cheapest edge which expands the single tree.

## Power Grid and Prim

## Prim Code

```
for v in G.V {
v.key = MAXINT;
v.parent = null; }
root.key = 0;
A = [];
PQ = new PriorityQueue(G.V);
while PQ.notEmpty() {
u = PQ.extract-min();
A.push(u);
for v in u.nbrs {
if v in PQ && v.key > weight(u,v) {
v.key = weight(u,v);
v.parent = u; } } }
```