Searching on the graph

Discrete Math 2
 Content
• Graph depth-first search algorithm
• Graph breadth-first search algorithm
• Application of depth-first search and breadth-first
search algorithms

2
Depth First Search (DFS)
 Idea
• During the search, prioritize "depth" over "width"
– Go down as deep as you can before turning back.
• Starting at a certain vertex v0 , select any vertex u adjacent to v0 and take it
as the next traversal vertex.
– The next traversal is done in the same way as for vertex v0 with the starting vertex u.
• To check that each vertex is traversed exactly once, we use an array[] of n
elements (corresponding to n vertices) :
– If the vertex u has been traversed, the corresponding element in the array[u] has the
value FALSE.
– Otherwise, if the vertex has not been traversed, the corresponding element in the
array has the value TRUE.

4
 DFS algorithm representation
DFS(u) can be described by the following recursive procedure:
DFS algorithm (u): //u is the vertex to start traversing
Begin
<Visit u vertex>; //Browse the vertex u
chuaxet[u] := FALSE; //Confirm the vertex u have browsed
for each v  Ke(u) do //Take each vertex v  Ke(u).
If (chuaxet[v] ) then //If vertex v has not been checked
DFS(v); //Depth traversal starting from vertex v
EndIf;
EndFor;
End.
5
DFS(u) algorithm uses the stack
(Recursion elimination)

6
 DFS Algorithm Complexity
• DFS(u) algorithm complexity depends on the graph representation
method.
– The algorithmic complexity is O(n2 ) in case the graph is represented as an
adjacency matrix, where n is the number of vertices of the graph.
– The algorithmic complexity is O(nm) in case the graph is represented as an edge
list, where n is the number of vertices of the graph, m is the number of edges of
the graph.
– Algorithm complexity is O(max(n,m)) In the case of a graph represented as an
adjacency list, where n is the number of vertices of the graph, m is the number
of edges of the graph.

7
 Ex: DFS algorithm (1/3)
Example 1: Let a graph of 13 vertices as shown in the
figure. Let’s debug the DFS(1) algorithm.

8
Ex: DFS algorithm (2/3)

9
Ex: DFS algorithm (3/3)

10
 Example 2

Let a graph of 13 vertices be

represented as an adjacency matrix
as shown on the right.
▪ Show the result of algorithm in
DFS starting at vertex u=1.
▪ Specify the state of the stack and
the set of vertices traversed at
each execution step.

11
Example 2: DFS(1) algorithm

12
 Algorithm Implementation
• Init() function: reads data from the file dothi.in and sets the array chuaxet[u] =True
(u=1, 2,..,n).
• DFS_Dequi function: Implement DFS(u) algorithm by recursion.
• DFS_Stack function: Implement the DFS(u) algorithm based on the stack.

See illustrative code 13

Breadth First Search Algorithm
 Idea
• During the search process, prioritize “width” over “depth”
• Search around before going any deeper
• Vertex loaded into the queue is u
– vertices adjacent to u (v 1 , v 2 , . . ., v k) are loaded into the queue if it is not already considered.
• The next traversal is started from the vertices still present in the queue.
• The algorithm stops when the queue is empty.

15
BFS Algorithm

16
 BFS Algorithm Complexity
• Algorithm complexity BFS(u) depends on the method of graph
representation.
– The algorithmic complexity is O(n2 ) in case the graph is represented as an
adjacency matrix, where n is the number of vertices of the graph.
– The algorithmic complexity is O(nm) in case the graph is represented as an edge
list, where n is the number of vertices of the graph, m is the number of edges of
the graph.
– The algorithmic complexity is O(max(n,m)) in case the graph is represented as an
adjacency list, where n is the number of vertices of the graph, m is the number
of edges of the graph.

17
 Ex: BFS algorithm (1/2)

Let a graph of 13 vertices be

represented as an adjacency matrix as
shown in the figure below.
▪ Show the result of algorithm in BFS
starting at vertex u=1?
▪ Specify the state of the queue and
the set of vertices to be traversed at
each execution step.

18
Ex: BFS algorithm (2/2)

19
 Note
• With undirected graphs
– If DFS(u) = V or BFS(u) = V, we can conclude that
the graph is connected.
• With directed graph
– If DFS(u) = V or BFS(u) = V, we can conclude that
the graph is weakly connected.

20
 Algorithm Implementation
• Init() function: reads data from the file dothi.in and sets the array
chuaxet[u] =True (u=1, 2,..,n).
• BFS function: Implement the BFS(u) algorithm using a queue.

See illustrative code

21
Application of DFS and BFS algorithms
 Some Applications of DFS and BFS

• Traverse all connected components of the graph.

• Find the path from vertex s to vertex t on the graph.
• Traverse the cut vertices on the undirected graph.
• Traverse the bridges on an undirected graph.
• Check and find the directionality of the undirected graph (định chiều đồ thị).
• Determine strong connectivity on directed graphs.
• Determine weak connectivity on directed graphs.
• List the strongly connected components of a directed graph.

23
Determine the connected components of the graph
• Problem statement:
– Given an undirected graph G=<V,E>, where V is the vertex set, and E is the
edge set. Let’s determine the connected components of G =<V,E>?
• Algorithm:

24
 Ex: Algorithm
The graph is represented as an adjacency matrix:

• Result:
– Connected component 1: BFS(1) = { 1, 3, 5, 7, 9, 11, 13}.
– Connected component 2: BFS(2) = {2, 4, 6, 8, 10, 12}.

25
 Algorithm Implementation
• Init() function: Reads data and starts the array chuaxet[u] = True (1  u  n).
• BFS(u), DFS(u) function: Two breadth-first and depth-first traversal algorithms
are used to determine connected components.

See illustrative code

26
Find the path between the vertices on the graph
• Problem statement
– Given a graph G =<V, E> (directed or undirected), where V is the vertex set,
and E is the edge set. Find the path from vertex s  V to vertex t  V?
• Algorithm:
– If t ∈ DFS ( s ) or t ∈ BFS(s) then we can conclude that there is a path from s to
t on the graph, otherwise there is no path.
– To record the path we use array before[] includes n elements (n = |V|)
• Initialization before[u] =0 for all u .
• Every time v Ke(u) is put on the stack (if using DFS ) or queue (if using BFS) we
record before[v] = u .
• If DFS or BFS fails to traverse to vertex t, then before [t] =0, we conclude that there
is no path from s to t .

27
Find the path between the vertices on the graph
Using DFS

28
Find the path between the vertices on the graph
Using BFS

29
Find the path between the vertices on the graph
Record the path

30
 Ex: Algorithm
Find the path from
vertex 1 to vertex
13 on the graph
represented as an
adjacency matrix as
shown next:

31
Ex: DFS(1) algorithm

32
 Ex: the BFS(1) algorithm

• Note:
– The path from vertex s to vertex t according to BFS algorithm goes through at least
the edges of the graph (the smallest length).
33
Algorithm Implementation

See illustrative code

34
 Strong connectivity on directed graphs
• Problem statement:
– A directed graph G=<V,E> is strongly connected if there is a path between any two of
its vertices.
– Given a directed graph G = <V,E>. Check if G is strongly connected or not?
• Algorithm:

35
 Ex: Algorithm
Let’s determines
whether the
directed graph G
=<V,E> is
represented as a
strongly connected
adjacency matrix?

36
Ex: Check strong connectivity

37
 Algorithm Implemetation
• Procedure Read-Data(: Read the adjacency matrix
representing the graph in the file dothi.in.
• Procedure ReInit(: Initialize the value for the chuaxet[]
array.
• Procedure DFS(u): The DFS algorithm starts at vertex u.
• Procedure BFS(u): The BFS algorithm starts at vertex u.
• Strong-Connective() function: Check the strong
connectivity of the graph.

See illustrative code

38
 Browse the cut vertices
• Problem statement
– Given undirected graph G =<V, E>. The vertex u  V is called cut vertex if removing the
vertex u along with the edges connected to u increases the connected component of the
graph.
– Given an undirected graph G =<V, E>, find the cut vertices of G?
• Algorithm:
– DFS() or BFS(), set the value chuaxet[u] = False
– The traversal will be performed at any vertex v  u .
• If DFS(v) = V\{u} or BFS(v) = V\{u} :
– newly obtained graph also has only 1 connected component
– Conclusion u not a cut vertex .
• If DFS(v)  V\{u} or BFS(v)  V\{u} :
– Then u is the cut vertex because the number of connected components of the graph has increased.

39
Algorithm to browse the cut vertices of the graph

40
 Ex: Algorithm
The undirected graph
G=<V,E> represented
as an adjacency
matrix.
Browse cut vertices?

41
Ex: Browsing the vertices of the graph

42
 Algorithm Implementation
• Procedure Read-Data(): Read the adjacency matrix
representing the graph in the file dothi.in.
• Procedure ReInit(): Initialize the value for the chuaxet[]
array.
• Procedure DFS(v): The DFS algorithm starts at vertex v.
• Procedure BFS(v): The BFS algorithm starts at vertex v.

See illustrative code

43
 Browse bridges
• Problem statement
– Given undirected graph G =<V,E>. Edge e  E is bridgesif removing e increases the
connected component of the graph.
– C for an undirected graph G = <V,E>, find all the edges of the graph.
• Algorithm:
– For a graph represented as an adjacency matrix:
• Removing the edge e=(u,v)  E from the graph is done by giving the elements A[u][v]=0 and
A[v][u]=0.
– For a graph represented as an adjacency list:
• Adjacency list of vertex u, remove vertex v , Ke(u) = Ke(u)\{ v }
• Adjacency list of vertex v, remove vertex u , Ke(v) = Ke(v)\{ u }.

44
Algorithm for browsing the bridges of a graph

45
 Ex: Algorithm
• The undirected
graph G=<V,E>
which is represented
as an adjacency
matrix.
• Browse bridges?

46
Ex: Browsing the edges of the graph

Conclusion: bridges (3,5), (9,10) 47

 Algorithm Implementation
• Procedure Read-Data(): Read the adjacency matrix
representing the graph in the file dothi.in.
• Procedure ReInit(): Initialize the value for the chuaxet[]
array.
• Procedure DFS(u): The DFS algorithm starts at vertex u.
• Procedure BFS(u): The BFS algorithm starts at vertex u.

See illustrative code

48
Browse strongly connected components of a graph

• Strongly connected component of a graph is a subgraph of G where

there is a path between any two vertices of the subgraph.
• Problem:
– List all strongly connected components of a directed graph G=<V,E>

49
 Tarjan's algorithm for finding strongly connected
components
• Idea: Depth-first search starts from an arbitrary vertex
– not consider any previously extracted vertices.
– Strongly connected components form the subtrees of the search tree, the
root of which is the root of strongly connected components .
– The vertices are put on a stack in the order in which they were examined.
• When the search returns a subtree, the vertices are removed from the stack and it is
determined whether each removed vertex is the root of a strongly connected
component.
• If a vertex has been determined to be the root of a strongly connected component, then
it and all previously extracted vertices form the strongly connected component.

50
 Tarjan's algorithm for finding strongly
connected components
• Algorithm Description:
– The root vertex is the first vertex of the strongly connected component found during
depth-first search.
• Once a vertex has been identified as a root vertex, after visiting that vertex, all vertices in
the stack from the root upwards form a complete strongly connected component.
– To find the original vertex , each vertex v is assigned a search index v.index, where the
index of the vertices is consecutively ranked in the order in which they were found.
– In addition, each node also stores a v.lowlink value equal to the minimum index of
vertices that can be reached from v, including v itself.
– v.lowlink value is always less than or equal to v.index .
• Hence v is the root of a strongly connected component if and only if v.lowlink = v.index .
– Note: The v.lowlink value is calculated during depth-first search.

51
 Pseudocode (Tarjan)
Input: Graph G = (V, E)
Output: strongly connected components (sets of vertices)
index:= 0
S:= empty //Stack
for each vertex v in the set V do
if (v.index undefined) then //vertex v has not been traversed
strongconnect(v)
end if
function strongconnect(v) //Set the depth index for v so that the
unused index is minimal
v.index:= index
v.lowlink:= index
index:= index + 1
S.push(v)

52
 Pseudocode (Tarjan), cont’d
//See next vertex of v
for each (v, w) in E do
if (w.index undefined) then
//Next vertex w is not visited yet; recursively visit it
strongconnect(w)
v.lowlink:= min(v.lowlink, w.lowlink)
else if (w is in S) then
// The next vertex w is in the stack S (visited) and therefore in the
currently strongly connected component v.lowlink:= min(v.lowlink,
w.index )
end if
//If v is the root node, remove from the stack and create a strongly
connected component
if (v.lowlink = v.index) then
//start a strongly connected component
repeat
w:= S.pop()
Add w to the current strong conjunction
until (w = v)
Output current strongly connected component
end if
end function
53
Illustration (strongly connected component)

54
 Graph directionality problem (1/2)
• Definition
– The dimensionality of a connected undirected graph is the transformation of a
connected undirected graph into a strongly connected directed graph.
– The undirected graph G =<V,E> that can be transformed into a strongly
connected directed graph by directing each undirected edge to a directed arc is
called a directional graph.

55
 Graph directionality problem (2/2)
• Theorem
– A connected undirected graph G =<V, E> is directional if and only if all
edges e  E are not bridges.
• Problem
– Given a connected undirected graph G = <V,E>. Let's direct the graph G so
that we can get a strongly connected directed graph.
• Some issues (sub-problems):
– Prove that the undirected graph is directional.
– Indicates a directionality on an undirected graph.
– Write a program to check if the undirected graph is dimensional or not?

56
 Sub-problem 1: Prove that the graph is directionable
• Method 1: Prove that a undirected graph is directional if the graph is strongly
connected.
– That is, we use BFS or DFS traversal algorithm to traverse the graph from every vertex of
the directed graph.
– If at every vertex we have a weakly connected graph (ie. strongly connected graph), then
conclude: the graph is directionable
• Method 2: The undirected graph is directional if all its edges are not bridges.

– Thus, we only need to check all edges of the graph to see if it is a bridge or not.

57
 Sub-problem 2: Determine the direction of the Graph

• Specify the forward and reverse direction for the graph.

– The forward direction is the direction of the edge going from vertex u
to other vertices.
– The reverse direction is the direction of the remaining vertices of the
graph to u.

58
 Illustration
• Given the graph as below, prove the graph is dimensionable.
• We have a table:
Step Edge BFS(i) Bridge

1 (1,2) 1.3.4.2.5 No
2 (1,3) 1.2.4.3.5 No
3 (1,4) 1.2.3.4.5 No
4 (2,4) 1.2.3.4.5 No
5 (2,3) 1.2.3.4.5 No
6 (2.5) 1.2.3.4.5 No
7 (3, 4) 1.2.3.4.5 No
8 (3.5) 1.2.3.4.5 No

• Sub-problem 1 : The graph has no bridge, so it is dimensionable.

• Sub-problem 2 : Showing the forward and reverse arcs:
• The forward arc: (from vertex 1 ) there is (1>2),(2>3).(3>4),(3>5)
• Reverse arc: (4.1) (3.1) (4.2) (5.2)
59
 Exercise 1
• The undirected graph be
represented as an adjacency
matrix as shown below. Let's:
a) Present the algorithm BFS(u)
b) Debug algorithm BFS(u) starts at
vertex u=1 ? Specify the
intermediate result for each
execution step.
c) Debug algorithm BFS(u) starts at
vertex u=7 ? Specify the
intermediate result for each
execution step.

60
 Exercise 2
• The undirected graph be
represented as an adjacency
matrix as shown below. Let's:
a) Present the DFS(u) algorithm
b) Debug DFS(u) algorithm starting at
vertex u=1 ? Specify the
intermediate result for each
execution step.
c) Debug DFS(u) algorithm starting at
vertex u=7 ? Specify the
intermediate result for each
execution step.

61
 Exercise 3
• The undirected graph be
represented as an adjacency
matrix as shown below. Let's:
a) Describe the algorithm for
traversing connected
components of a graph?
b) Debug the algorithm on the
given graph? Specify the
intermediate result for each
execution step.

62
 Exercise 4
• The undirected graph be represented
as an adjacency matrix as shown
below. Let’s:
a) Using BFS algorithm, build an algorithm
to find the path from vertex s to vertex t
on the graph?
b) Find the path from vertex s=1 to vertex
t=13 on the given graph? Specify the
intermediate result for each execution
step.
c) Write a program to find the path from s
to t using adjacency matrix.

63
 Exercise 5
• The undirected graph be
represented as an adjacency matrix
as shown below. Let’s:
a) Using DFS algorithm, build an algorithm
to find the path from vertex s to vertex
t on the graph?
b) Find the path from vertex s=1 to vertex
t=13 on the given graph? Specify the
intermediate result for each execution
step.
c) Write a program to find the path from
s to t using adjacency matrix.

64