## Graphs p3 (DFSp2 and Weights)

#### Andy Novocin

## Problem of the day

### Draw on Board

## Edge Classification

**Base case** Tree Edge (parent to child)

### Forward Edge (jump beyond children)

### Back Edge (jump past parents)

### Cross Edge (jump to cousins)

## DFS (undirected) no cross

## DFS (undirected) no forward

## DFS directed anything goes

## Classify edge pseudo-code

```
def classify(x,y):
if (y.parent == x):
return "TREE"
elif y.discovered() and !y.processed():
return "BACK"
elif y.processed() and (y.dt > x.dt):
return "FORWARD"
elif y.processed() and (y.dt < x.dt):
return "CROSS"
```

## Detecting Cycles

### No back edge == No cycles

### Detecting back edges is mildly subtle

### NOTE: In undirected this is \( \mathcal{O}(|V|) \leq \mathcal{O}(|V|+|E|)\)

## DAG => No Cycle

### Note that you cannot topological sort with cycles.

### But you can almost topological sort.

## Articulation Vertices

### Graphs are networks

### Weak points are targets or key defense points

### Back edges create security cables

## Articulation Brute Force

### Test if connected (using BFS or DFS)

### For each vertex, remove it, test again, reinsert

## Articulation In One Pass

### \(v\) is an Articulation Vertex if and only if:

### \(v\) is not a leaf, and there is a subtree of \(v\) which has no back edges that reach beyond \(v\).

## Guide to the code

#### In the book there is an implementation

#### Cliff's Notes version:

#### Figure out the farthest back reachable using only neighbors.

#### If this answer is earlier than parent's answer then pass it along.

## Three cases

### Root cut-node (root has more than 1 tree child)

### Bridge cut-node (my oldest reachable ancestor is me) then me and parent are cut-nodes

### Parent cut-node (oldest reachable is non-root parent (in odd ways)) then parent is cut-node

## Strongly connected components

### In directed graphs can detect if connected by traversal and traversal of 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.

## ICUP3

### Find the SCC for problem 5-2

## Work problems

### If we have time work HW and ask questions