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

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