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