Graph traversal: DFS

Andy Novocin

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)
  

Daily "Challenge"

Draw on board

ACM Challenge

Show the page

Right-side Challenge

Examine CSS Zen Garden

Examine Twitter Bootstrap

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

Getting Dressed (ICUP)

Applications of Top. Sort

Ordering instructions that have requirements

Counting paths

ICUP

22.4-2 22.8 CLRS

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