## Graph traversal: DFS

#### Andy Novocin

## ICU-0.1 Can this be two-colored?

## Bipartite Graph Detection

```
for v in vertices:
v.color = "none"
s = vertices[0]
s.color = "color1"
bipartite = True
BFS(G,s) //using extra sub-routines
def process_edge(u,v):
if (u.color == v.color):
bipartite = False
v.color = opposite_color(u.color)
```

## ICU-0.2 Now use algorithm

## Daily "Challenge"

## Draw on board

## ACM Challenge

## Show the page

## Unsmenatic vs Semantic

```
<button type="button" class="btn btn-primary btn-lg">
Large button
</button>
<p class="text-uppercase">
Uppercased text.
</p>
```

```
<footer>
<a href="http://validator.w3.org/check/referer"
title="Check the validity of this site’s HTML"
class="zen-validate-html">
HTML
</a>
</footer>
```

## Depth First Search

```
for u in G.V:
u.color = white
u.p = NULL
time = 0
for u in G.V:
if u.color == white:
DFS-VISIT(u)
```

## Depth First Search Recursive

```
DFS-VISIT(u):
time += 1
u.dt = time
u.color = gray
for v in u.neighbors:
if v.color == white:
v.p = u
DFS-VISIT(v)
u.color = black
time += 1
u.ft = time
```

## Backtracking as General Strategy

### If you need an exhaustive search then DFS is your prototype

### More naturally recursive than BFS

## Parenthesis Property

### Pick any \(u\) and \(v\) from \(G\). 1 of 3 possibilities:

### \([u.dt,u.ft] \cap [v.dt, v.ft] = \emptyset \)

### \([u.dt,u.ft] \cap [v.dt, v.ft] = [u.dt, u.ft]\)

### \([u.dt,u.ft] \cap [v.dt, v.ft] = [v.dt, v.ft]\)

## Topological Sorting

### DAG (Directed Acyclic Graph)

### Can I arrange vertices left to right in order?

## Top. Sort

### Call DFS(G), compute \(v.ft\) for all vertices

### As each vertex is finished put it at the front of a linked list

## Applications of Top. Sort

### Ordering instructions that have requirements

### Counting paths

## 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

### Draw Picture

## DFS (undirected) no forward

### Draw Picture

## Detecting Cycles

### No back edge == No cycles

### Detecting back edges is mildly subtle

## 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\).