APPLIED ALGORITHMS
APPLIED ALGORITHMS
DEPTH FIRST SEARCH (DFS) AND APPLICATIONS
3
CONTENTS
• Depth First Search (DFS)
• DFS tree and và structure Num, Low
• Find bridges (cạnh cầu)
• Find articulation vertex (đỉnh khớp)
• Find strongly connected component (thành phần liên thông mạnh)
4
Depth First Search (Tìm kiếm theo chiều sâu)
• Depth First Search is a basic graph traversal technique (visiting every vertex and every edge of the
graph).
• The algorithm can answer the question, does there exist a path from vertex 𝑢 to vertex 𝑣 on
graph 𝐺 or not, if yes, indicate it.
• The algorithm not only answers whether there is a path from 𝑢 to 𝑣, but it can answer which
other vertices on the graph 𝐺 can be reached from u.
• The traversal order in DFS follows the Last In First Out (LIFO) mechanism, and starts from a certain
starting vertex 𝑢.
• Can use backtracking or stack to implement
• The complexity: 𝑂( 𝑉 + 𝐸 ), where 𝑉 is the vertex set and 𝐸 is the edge set of the graph 𝐺, as each
vertex and edge of 𝐺 is visited exactly once.
5
Implement idea
1. DFS(u, V, A) {
• Graph G = (V, E) is represented by an
adjacent list 2. visit(u); // assign visited[u] = true
• A[u]: list of adjacent nodes of u 3. for v in A[u] do {
• Marking array: 4. if not visited[v] then {
• visited[u] = true means u was 5. DFS(v, V, A);
visited, and visited[u] = false 6. }
means that u is not visited 7. }
8. }
9. DFS(V, A){
10. for u in V do { visited[u] = false; }
11. for u in V do {
12. if not visited[u] then
13. DFS(u, V, A);
14. }
15. }
6
CONTENTS
• Depth First Search (DFS)
• DFS tree and và structure Num, Low
• Find bridges (cạnh cầu)
• Find articulation vertex (đỉnh khớp)
• Find strongly connected component (thành phần liên thông mạnh)
7
DFS tree
• The trace of the depth-first search will form a tree
a a
b f
b f
c g c g
8
DFS tree
• The trace of the depth-first search will form a tree
• Some kind of edge in the search process:
• Tree Edge (Cạnh cây): The edge along which a new vertex is
visited from one vertex, for example the black edge in the figure
a
• Back Edge (Cạnh ngược): The edge going from descendant to
ancestor, for example the red edge (g,a) in the figure
• Forward Edge (Cạnh xuôi): The edge going from ancestors to
b f
descendants, for example the blue edge (a,c) in the figure
• Crossing Edge (Cạnh vòng): The edge connecting two unrelated
vertices, for example the dashed purple edge (c,g) in the figure
c g
9
DFS tree
• Arrays 𝑁𝑢𝑚 and 𝐿𝑜𝑤 store information of
vertices in DFS tree:
• 𝑁𝑢𝑚[𝑢]: visit order of vertex u in DFS
• 𝐿𝑜𝑤[𝑢]: has the smallest value among
the following values:
• 𝑁𝑢𝑚[𝑣] if (𝑣, 𝑢) is a back edge
• 𝐿𝑜𝑤[𝑣] if 𝑣 is a child of 𝑢 in DFS
tree
• 𝑁𝑢𝑚[𝑢]
10
Example
11
Implementation ideas
1. DFS(u, V, A, p) {
• p[v]: parent of v discovered during
the DFS 2. T += 1; Num[u] = T; Low[u] = T;
• Num[u] = 0: node u has not been 3. for v in A[u] do {
visited yet 4. if v = p[u] continue;
• Num[u] > 0: is visited, and Num[u] is 5. if Num[v] > 0 then { // v was visited
the order that u is visited 6. Low[u] = min(Low[u], Num[v]);
7. } else {
8. p[v] = u;
9. DFS(v, V, A, p);
10. Low[u] = min(Low[u], Low[v]);
11. }
12. }
13. }
12
CONTENTS
• Depth First Search (DFS)
• DFS tree and và structure Num, Low
• Find bridges (cạnh cầu)
• Find articulation vertex (đỉnh khớp)
• Find strongly connected component (thành phần liên thông mạnh)
13
Find bridge (cầu) in the graph
• Definition: A bridge is an edge of an undirected graph, so that removing this edge from the graph
will increase the number of connected components.
• Comment: A forward edge (𝑢, 𝑣) is bridge if and only if 𝐿𝑜𝑤[𝑣] > 𝑁𝑢𝑚[𝑢]
14
Find bridge (cầu) in the graph
• Definition: A bridge is an edge of an undirected graph, so that removing this edge
from the graph will increase the number of connected components.
• Comment: A forward edge (𝑢, 𝑣) is bridge if and only if 𝐿𝑜𝑤[𝑣] > 𝑁𝑢𝑚[𝑢]
15
Implementation idea
DFS(u) {
• p[v]: parent of v discovered during
the DFS T += 1; Num[u] = T; Low[u] = T;
• Num[u] = 0: node u has not been for v in A[u] do {
visited yet if v = p[u] continue;
• Num[u] > 0: is visited, and Num[u] is if Num[v] > 0 then { // v was visited
the order that u is visited Low[u] = min(Low[u], Num[v]);
} else {
p[v] = u;
DFS(v);
Low[u] = min(Low[u], Low[v]);
if Low[v] > Num[u] then (u,v) is a bridge;
}
}
}
16
CONTENTS
• Depth First Search (DFS)
• DFS tree and và structure Num, Low
• Find bridges (cạnh cầu)
• Find articulation vertex (đỉnh khớp)
• Find strongly connected component (thành phần liên thông mạnh)
17
Find articulation vertex (đỉnh khớp)
• Definition: In an undirected graph, a vertex is called an
articulation vertex if removing this vertex and edges having it as
end point from the graph will increase the number of connected
components of the graph.
• Comment: Vertex 𝑢 vertex is called an articulation vertex if:
• Either vertex 𝑢 is not the root of DFS tree and 𝐿𝑜𝑤[𝑣] ≥
𝑁𝑢𝑚[𝑢] (where 𝑣 is any direct child of 𝑢 in the DFS tree);
• Or vertex 𝑢 is the root of the DFS tree and has at least 2
direct children.
18
Implementation idea
DFS(u) {
• p[v]: parent of v
discovered during the DFS T += 1; Num[u] = T; Low[u] = T;
for v in A[u] do {
• Num[u] = 0: node u has
not been visited yet if v = p[u] continue;
if Num[v] > 0 then { // v was visited
• Num[u] > 0: is visited, and
Num[u] is the order that u Low[u] = min(Low[u], Num[v]);
is visited } else { // visit v
• numChild[u]: number of p[v] = u; numChild[u] += 1;
children of u DFS(v);
Low[u] = min(Low[u], Low[v]);
if u = p[u] then { // u là đỉnh xuất phát DFS (root)
if numChild[u] >= 2 then { u is an articulation point; }
} else { if Low[v] >= Num[u] then u is an articulation point; }
}
}
}
19
CONTENTS
• Depth First Search (DFS)
• DFS tree and và structure Num, Low
• Find bridges (cạnh cầu)
• Find articulation vertex (đỉnh khớp)
• Find strongly connected component (thành phần liên thông mạnh)
20
Find Strongly Connected Components
• Breadth-First-Search (BFS) and Depth-First-Search (DFS) can easily find all connected
components in an undirected graph. However, finding all strongly connected components is not
simple for directed graph.
• Note: A strongly connected component is a maximum subset of vertices such that between
any two vertices there is always a path from one vertex to the other and vice versa.
• DFS search trees can be used to find
• all strongly connected components?
21
Thuật toán Tarjan
• Observation: After analyzing the DFS tree, if at
a vertex 𝑢, 𝑁𝑢𝑚[𝑢] = 𝐿𝑜𝑤[𝑢], then we have a
strongly connected component following the
process of traversing the tree from 𝑢.
• Use Stack ST to list vertices in a strongly
connected component.
• Marking: inStack[u] = true means that u is in the
Stack ST
• After visiting u and the edge (u,v) is
discovered in which v was visited → We can
recognize the edge (u,v) is a back eddge or
crossing edge:
• inStack[v] = true: (u,v) is a back edge
• inStack[v] = false: (u,v) is a crossing edge
• Complexity: 𝑂( 𝑉 + 𝐸 )
22
Implementation idea
DFS(u) {
T += 1; Num[u] = T; Low[u] = T; ST.push(u); inStack[u] = true;
for v in A[u] do {
if v = p[u] continue;
if Num[v] > 0 then { // v was visited
if inStack[v] then Low[u] = min(Low[u], Num[v]); // (u,v) is a back edge
} else { // visit v
p[v] = u; DFS(v); Low[u] = min(Low[u], Low[v]);
}
}
if Low[u] = Num[u] then {// retrieve a strongly connected component stored in stack ST
while ST not empty do { x = ST.pop(); print(x); inStack[x] = false; if x = u then break; }
}
}
23
THANK YOU !
24
