DFS II
Concept
DFS tree
Cut verticies
- vertex with at least 2 DFS tree children, 2 children mean no path between the two subtrees
FindCutVertices(G):
for each vertex u:
discover[u] = UNVISITED
parent[u] = NIL
isCut[u] = false
time = 0
for each vertex u:
if discover[u] == UNVISITED:
CutDFS(u)
return vertices u with isCut[u] == true
CutDFS(u):
time = time + 1
discover[u] = time
low[u] = discover[u]
children = 0
for each v in Adj[u]:
if discover[v] == UNVISITED:
parent[v] = u
children = children + 1
CutDFS(v)
low[u] = min(low[u], low[v])
if parent[u] != NIL and low[v] >= discover[u]:
isCut[u] = true
else if v != parent[u]:
low[u] = min(low[u], discover[v])
if parent[u] == NIL and children >= 2:
isCut[u] = true
every edge in a graph G is a back edge in its DFS tree
Start and Finish times ^1d70f3
for every pair of verticies (u,v) in G, (start[u], finish[u]) and (start[v], finish[v]) are either disjoint or one is contained in the other
Application
Cycle with
- Run DFS in any connected component, recording
parentanddepth. - Choose a leaf (v) of the resulting DFS tree.
- Among all neighbors of (v), choose (u) with minimum depth.
- Follow parent pointers from (v) up to (u).
- Close this path using the edge (uv).
FindLongCycle(G):
run DFS from any vertex
record parent, depth, and number of DFS children
choose a visited vertex v with no DFS children
u = a neighbor of v having minimum depth
path = [v]
x = v
while x != u:
x = parent[x] // traverse up the tree
append x to path
return path with the closing edge from u to v
- neighbour of a leaf in DFS tree is ancestor