Biconnected Components

CS 312
 Objectives
• Formulate problems as problems on graphs
• Implement iterative DFS
• Describe what a biconnected component is
• Be ready to start project 2
 Problems on Graphs
• What to store in each node of the graph?
• What does it mean for two nodes to be
connected in the graph?
• What property do I want to analyze about the
graph?
– Then select or adapt an algorithm.
 Generic graph exploration
Explore (G, v)
Input: G = (V,E) and v in V
Output: visited(u) is true u for all u reachable
from v.
visited(v) = true
previsit(v)
for each edge (v,u) E
if not visited(u) then explore (u)
postvisit (v)
 Iterative DFS version
ExploreIterDFS (G, v)
Input: G = (V,E) and v in V
Output: visited(u) is true u for all u reachable
from v.
[Link](v)
if ([Link]())
v = [Link]
visited(v) = true
previsit(v)
for the next edge (v,u) E
if not visited(u) then [Link](u)
if all edges from v have been traversed then
[Link](v)
postvisit (v)
 Iterative DFS version
ExploreIterDFS (G, v)
Input: G = (V,E) and v in V
Output: visited(u) is true u for all u reachable
from v.
[Link](v)
if ([Link]())
v = [Link]
visited(v) = true
previsit(v)
for the next edge (v,u) E
if not visited(u) then [Link](u)
if all edges from v have been traversed then
[Link](v)
postvisit (v)
 Definitions
• Biconnected component
– The largest set of edges such that…
– There is a set of EDGES for which there is a simple
cycle between every edge
– Or it is a single edge
• Bridge
– Bicconnected component of size 1
• Separating vertex
– Vertex which can be deleted to partition the graph.
 Example

f
g
b

c
d
 Example

f
g
b

c
d
DFS Tree
 “Low” numbering
• “pre” ordering
• “low” numbering
Separating Vertices

How does that translate into a test

on low and pre?
 The Idea for the Algorithm
• If you can find low and pre, you can identify
separating vertices.
– You can use DFS to find low and pre.
– Pre is easy.
• If you can find separating vertices, then you
can use a second DFS to find biconnected
components.
– Keep in mind that the biconnected components
are edges not vertices.
 Example
a
a
f ab
g b bg
b gc
g cd
e dg pop
c e
c
d
d f

h h
 Example
a
a,1
f pre numbering.
g b,2
b
g,3
e
c,4 e,7
c
d
d,5 f,8

h h,6
 Example
a
a,1,1
f low numbering.
g b,2,1
b
g,3,3
e
c,4,3 e,7,3
c u is a sep. vertex iff
d
there is a child v of u s.t.
d,5,3 f,8,3
pre(u) “< or =“ low(v)
h h,6,6
 Example
a
a,1,1
f
g b,2,1
h,6,6
b d,5,5
g,3,3
c,4,4
e
g,3,3
c,4,3 e,7,3 b,2,2
c
d a,1,1
d,5,5 f,8,8
(vertex, pre, lowest low
h h,6,6 so far)
Computing low.
Always initialize [Link] = [Link]
When follow edge (u,v) and v is visited (and v != the DFS parent of u), [Link] = min ([Link], [Link])
When pop u off DFS stack, pass low to parent.
If u’s low is lower than it’s parent, then update parent.
 Example
a
a,1,1 d is visited
f but, d is h’s
b,2,1 d,5,5 dfs parent
g
h,6,6
b d,5,5
g,3,3 Do nothing.
c,4,4
e
g,3,3
c,4,3 e,7,3 b,2,2
c
d a,1,1
d,5,5 f,8,8
(vertex, pre, lowest low
h h,6,6 so far)
Computing low.
Always initialize [Link] = [Link]
When follow edge (u,v) and v is visited, [Link] = min ([Link], [Link])
When pop u off DFS stack, pass low to parent.
If u’s low is lower than it’s parent, then update parent.
 Example
a
a,1,1 d is visited
f but, d is h’s
b,2,1 d,5,5 dfs parent
g
h,6,6
b d,5,5
g,3,3 Do nothing.
c,4,4
e
g,3,3
c,4,3 e,7,3 b,2,2
c
d a,1,1
d,5,5 f,8,8
(vertex, pre, lowest low
h h,6,6 so far)
Computing components
2nd DFS
use a stack of edges.
push a mark onto the edge stack with the child of a SV
when pop the child of an SV (in the node stack) pop back to the mark.