Graph Traversal

BFS & DFS

 Review of tree traversal methods
a
• Pre-order traversal
• In-order traversal b c
• Post-order traversal f
• Level traversal d e
g h i j
 Graph Search Methods
• A vertex u is reachable from vertex v iff there is a
path from v to u.

2
3
8
1

4
5
9
10

6
7 11
 Graph Search Methods
(traversal)
• A search method starts at a given vertex v and
visits/labels/marks every vertex that is reachable
from v.
2
3
8
1

4
5
9
10

6
7 11
 Graph Search Methods
• Many graph problems solved using a search
method.
▪ Finding Path(shortest) from one vertex to another.
▪ Check if the graph is connected?
▪ Find a (minimum) spanning tree.
• Commonly used search (traversal) methods:
▪ Breadth-first search.
▪ Depth-first search.
 Breadth-First Search
• Visit start vertex (selected by user) and put into
a FIFO queue.
• Repeatedly remove a vertex from the queue, visit
its unvisited adjacent vertices, put newly visited
vertices into the queue.
• BFS(G,1)
2
3

4
5
 Breadth-First Search Example

2
3
8
1

4
5
9
10

6
7 11

Start search at vertex 1.

 Breadth-First Search Example

2
3
FIFO Queue
8
1 1
4
5
9
10

6
7 11

Visit/mark/label start vertex and put in a FIFO queue.

 Breadth-First Search Example

2
3
FIFO Queue
8
1 1
4
5
9
10 Blue vertex is
visited
6
7 11

Remove 1 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 2 4
1

4
5
9
10

6
7 11

Remove 1 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 2 4
1

4
5
9
10

6
7 11

Remove 2 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 4 3 5 6
1

4
5
9
10

6
7 11

Remove 2 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 43 5 6
1

4
5
9
10

6
7 11

Remove 4 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 356
1

4
5
9
10

6
7 11

Remove 4 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 356
1

4
5
9
10

6
7 11

Remove 3 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 679
1

4
5
9
10

6
7 11

Remove 5 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8
1 79
4
5
9
10

6
7 11

Remove 7 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8
1 9
4
5
9
10

6
7 11

Remove 9 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8
1 8
4
5
9
10

6
7 11

Remove 9 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8 8
1

4
5
9
10

6
7 11

Remove 8 from Q; visit adjacent unvisited vertices;

put in Q.
 Breadth-First Search Example

2
3
FIFO Queue
8
1

4
5
9
10

6
7 11

Queue is empty. Search terminates.

 Example
start from 2, 7 and 9
• 2
• 3
• 8
• 1

• 4
• 5
• 9
• 1
0

• 6
• 7 • 11
 Breadth-First Search Property

• All vertices reachable from the start vertex

(including the start vertex) are visited.
Breadth-first-search
 Example start at 1

• 2
• 3
• 8
• 1 • 1
• 4 0
• 5 • 9 • 11

• 6
• 7
 Example start at 1

2
3
8
1 10
4
5 9 11

6
7
 Example start at 2

• 2
• 3
• 8
• 1 • 1
• 4 0
• 5 • 9 • 11

• 6
• 7
 Example start at 2

• 2
• 3
• 8
• 1 • 1
• 4 0
• 5 • 9 • 11

• 6
• 7
Finding a Path From Vertex v To
Vertex u

• Start a breadth-first search at vertex v.

• Terminate when vertex u is visited or when
Q becomes empty (whichever occurs first).
 Is The Graph Connected?

• Start a breadth-first search at any vertex of

the graph.
• Graph is connected iff all n vertices get
visited.
 Connected Components
• Start a breadth-first search at any as yet
unvisited vertex of the graph.
• Newly visited vertices (plus edges between
them) define a component.
• Repeat until all vertices are visited.
 Connected Components

2
3
8
1

4
5
9
10

6
7 11
 Spanning Tree

2
3
8
1

4
5
9

6
7

Breadth-first search from vertex 1.

Breadth-first spanning tree.
 Spanning Tree
• Start a breadth-first search at any vertex of
the graph.
• If graph is connected, the n-1 edges used to
get to unvisited vertices define a spanning
tree (breadth-first spanning tree).
 Depth-First Search

depthFirstSearch(v)
{
Label vertex v as reached.
for (each unreached vertex u
adjacenct from v)
depthFirstSearch(u);
}
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Start search at vertex 1.

Label vertex 1 and do a depth first search
from either 2 or 4.
Suppose that vertex 2 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 2 and do a depth first search

from either 3, 5, or 6.
Suppose that vertex 5 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 5 and do a depth first search

from either 3, 7, or 9.
Suppose that vertex 9 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 9 and do a depth first search

from either 6 or 8.
Suppose that vertex 8 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 8 and return to vertex 9.

From vertex 9 do a dfs(6).
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 6 and do a depth first search from

either 4 or 7.
Suppose that vertex 4 is selected.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 4 and return to 6.

From vertex 6 do a
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label vertex 7 and return to 6.

Return to
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Do a
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Label 3 and return to

5.
Return to 2.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to 1.
 Depth-First Search Example
2
3
8
1

4
5
9
10

6
7 11

Return to invoking method.

 Example
start from 2, 7 and 9
• 2
• 3
• 8
• 1

• 4
• 5
• 9
• 1
0

• 6
• 7 • 11
 Depth-First Search Properties
• Same properties with respect to path
finding, connected components, and
spanning trees.
• Edges used to reach unlabeled vertices
define a depth-first spanning tree when the
graph is connected.
• There are problems for which bfs is better
than dfs and vice versa.
Depth-first-search
 Graph Algorithms

Minimum Spanning Trees

54
Problem: Laying Telephone Wire

Central office

55
 Wiring: Naïve Approach

Central office

Expensive!

56
 Wiring: Better Approach

Central office

Minimize the total length of wire connecting the customers

57
Biconnected Components
 Articulation points of graph
In the connected graph G, a vertex V is said to be an
articulation point if and only if the deletion of vertex V
disconnects the graph into two or more non - components.
The presence of articulation points in a connected graph can
be an undesirable(un wanted) feature in many cases.

6
1 6
1 5
5
4
4 2 7
7
3
3 8
8
10 9
10 9
 Biconnected Graph
• A graph is biconnected iff it contains no
articulation points
8

7
 Biconnected Component
• If a connected graph G is not biconnected, it may be desirable to
determine a set of edges whose inclusion makes the graph biconnected
• Determining such a set of edges is facilitated if we know the maximal
subgraphs of G that are biconnected. G' = (V',E') is a maximal
biconnected subgraph of G if and only if G has no biconnected
subgraph G" = (V", E")
• A maximal biconnected subgraph is a Biconnected Component.

6
1
5 5
4 2 3 3
2 7
3 9 1
0 8
Depth First Spanning Tree(DFT)

8
6
1
7
1 5

2
9
6 2 7
4

3 3 8 10

4 10 9 5
 Biconnected Component
• If a connected graph G is not biconnected, it may be desirable to
determine a set of edges whose inclusion makes the graph biconnected
• Determining such a set of edges is facilitated if we know the maximal
subgraphs of G that are biconnected. G' = (V',E') is a maximal
biconnected subgraph of G if and only if G has no biconnected
subgraph G" = (V", E")
• A maximal biconnected subgraph is a Biconnected Component.

6
1
5 5
4 2 3 3
2 7
3 9 10
8
 Finding Articulation Points
• The root node of a depth first spanning tree is an articulation point iff it
has at least two children
• If u is any other vertex, then it is not an articulation point iff from every
child w of u it is possible to reach an ancestor of u using only a path
made up of descendents of w and a back edge.
• If this cannot be done for some child w of it, then u is an articulation
point.
• This observation leads to a simple rule to identify articulation points.
For each vertex u, define L[u] as follows:
L[u] = min {dfn[u],
min {L[w] | w is a child of u},
min {dfn[w] | (u, w) is a back edge}}
• If u is not the root, then it is an articulation point iff it has a child w
such that L[w] >= dfn[u].
Depth First Spanning Tree(DFT)

8
6
6
1 7
5 1 5
1

2 9
4 2 7 4 6 2 7

3 8 3 3 8 10

10 9 4 10 9 5
 A depth first spanning tree of graph
u L[u]
1
1
1 1
2
2 1
4
3 3 1
3 4 1
4 6
5 5 6
10 9 2
6 8
7
5
7 6
8 6
8 9 9 5
6 7

10
10 4
8
Algorithm for finding Articulation Points
Algorithm Art(u, v)
//It is assumed that the global array dfn is initialized to zero
//global variable num is initialized to 1. n is the number of vertices in G.
{
dfn[u] := num; L[u] := num; num := num + 1;
for each vertex w adjacent from u do
{
if (dfn[w] = 0) then
{
Art(w,u); // w is unvisited.
L[u] := min(L[u], L[w]);
}
else if (w != v) then L[u] := min(L[u],dfn[w]);
}
}
 Example – Finding Articulation
Points
0
u dfn[u] L[u]
0 1 1
3 1 5 5
2 3 3
3 2 2
2
4 4 3
5 6 3
4

1 5

Image Courtesy: www.hackerearth.com

Algorithm BiComp (u, v)
{
dfn [u] := num; L[u] := num; num := num + 1;
for each vertex w adjacent from u do
{
if ((v != w) and (dfn [w] < dfn [u])) then
add (u, w) to the top of a stack s;
if (dfn [w] = 0) then
{
BiComp (w, u); // w is unvisited.
L [u] := min (L [u], L [w]);
if (L [w] >= dfn [u]) then
{
write (“New bicomponent”);
repeat {
Delete an edge from the top of stack s;
Let this edge be (x, y);
Write (x, y);
} until (((x, y) = (u, w)) or ((x, y) = (w, u)));
}
}
else if (w != v) then L [u] : = min (L [u], dfn [w]);
}
}
 1 2
   
3 1-2 2-3
1-2
4
BiComp (1, 0)    
dfn [1] := 1; L[1] := 1; num := 2; 3-1 3-4
W=2 2-3 3-1
1-2 2-3
BiComp (2, 1)
dfn [2] := 2; L[2] := 2; num := 3; 1-2
W=3 =1
 
BiComp (3, 2) 3-4  
dfn [3] := 3; L[3] := 3; num := 4; 3-1 3-1
W=1 =1 2-3 2-3
1-2 1-2
BiComp (4, 3)
dfn [4] := 4; L[4] := 4; num := 5;
W=1

3 1 1 2 1 2

4 3 3
3