### Biconnected Components

```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.
stack.push(v)
if (stack.notEmpty())
v = stack.top
visited(v) = true
previsit(v)
for the next edge (v,u) E
if not visited(u) then stack.push(u)
if all edges from v have been traversed then
stack.pop(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.
stack.push(v)
if (stack.notEmpty())
v = stack.top
visited(v) = true
previsit(v)
for the next edge (v,u) E
if not visited(u) then stack.push(u)
if all edges from v have been traversed then
stack.pop(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
a
f
g
b
e
d
c
Example
a
f
g
b
e
d
c
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
bg
gc
cd
dg  pop
b
g
b
g
e
c
d
h
c
e
d
f
h
Example
 pre(u)
low(u)  min
 pre(w) where(v,w)is a backedge for a descendantv of u
a
a,1
f
pre numbering.
b,2
g
b
g,3
e
c
d
h
c,4
e,7
d,5
f,8
h,6
Example
 pre(u)
low(u)  min
 pre(w) where(v,w)is a backedge for a descendantv of u
a
a,1,1
f
low numbering.
b,2,1
g
b
g,3,3
e
c
d
c,4,3
e,7,3
d,5,3 f,8,3
h
h,6,6
u is a sep. vertex iff
there is a child v of u s.t.
pre(u) “< or =“ low(v)
Example
 pre(u)
low(u)  min
 pre(w) where(v,w)is a backedge for a descendantv of u
a
a,1,1
f
b,2,1
g
b
g,3,3
e
c
d
c,4,3
e,7,3
d,5,5 f,8,8
h
h,6,6
h,6,6
d,5,5
c,4,4
g,3,3
b,2,2
a,1,1
(vertex, pre, lowest low
so far)
Computing low.
Always initialize u.low = u.pre
When follow edge (u,v) and v is visited (and v != the DFS parent of u), u.low = min (u.low, v.pre)
When pop u off DFS stack, pass low to parent.
If u’s low is lower than it’s parent, then update parent.
Example
 pre(u)
low(u)  min
 pre(w) where(v,w)is a backedge for a descendantv of u
a
a,1,1
f
b,2,1
g
b
g,3,3
e
c
d
c,4,3
e,7,3
d,5,5 f,8,8
h
h,6,6
Computing low.
Always initialize u.low = u.pre
When follow edge (u,v) and v is visited, u.low = min (u.low, v.pre)
When pop u off DFS stack, pass low to parent.
If u’s low is lower than it’s parent, then update parent.
d,5,5
h,6,6
d,5,5
c,4,4
g,3,3
b,2,2
a,1,1
d is visited
but, d is h’s
dfs parent
Do nothing.
(vertex, pre, lowest low
so far)
Example
 pre(u)
low(u)  min
 pre(w) where(v,w)is a backedge for a descendantv of u
a
a,1,1
f
b,2,1
g
b
g,3,3
e
d
c
c,4,3
e,7,3
d,5,5 f,8,8
d,5,5
h,6,6
d,5,5
c,4,4
g,3,3
b,2,2
a,1,1
d is visited
but, d is h’s
dfs parent
Do nothing.
(vertex, pre, lowest low
so far)
h,6,6
h
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.
```