Graph Traversing and
Searching
S
BFS and DFS
S Breadth First Searching
S Depth First Searching
Breadth First Search
S There are many ways to traverse the graph, but
among them, BFS is the most commonly used
approach.
S It is a recursive algorithm to search all the
vertices of a tree or graph data structure.
S BFS puts every vertex of the graph into two
categories - visited and non-visited.
S It selects a single node in a graph and, after
that, visits all the nodes adjacent to the selected
node.
Applications of BFS algorithm
•BFS can be used to find the neighboring locations from a given
source location.
•In a peer-to-peer network, BFS algorithm can be used as a
traversal method to find all the neighboring nodes.
• BFS can be used in web crawlers to create web page indexes. It
is one of the main algorithms that can be used to index web
pages. It starts traversing from the source page and follows the
links associated with the page. Here, every web page is
considered as a node in the graph
.
•BFS is used to determine the shortest path and minimum
spanning tree.
Breadth-First Search (BFS)
Breadth-First Search (BFS)
Not
u x discovered
Discovered,
adjacent
v y white nodes
Discovered,
no adjacent
w z white nodes
Breadth-First Search (BFS)
u x
BFS(G, u):
1. Initialize the graph
v y color[u] gray
π[u] Nil
d[u] 0
for each other
w z vertex
color[u] white
Breadth-First Search (BFS)
u x Q
BFS(G, u):
2. Initialize the queue
v y QØ
Enqueue(Q, u)
w z
Breadth-First Search (BFS)
t=u
u x Q
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
w z
Breadth-First Search (BFS)
t=u
u Q r = x, v
x
BFS(G, u):
3. While Q ≠ Ø
v y 2) for each r adj to t
if color[r] = white
color[r] gray
π[r] t
w z d[r] d[t] + 1
Enqueue(Q, r)
Breadth-First Search (BFS)
t=u
u Q r = x, v
x
BFS(G, u):
3. While Q ≠ Ø
v y 3) color[t] black
w z
Breadth-First Search (BFS)
t=v
u x Q
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=v
u Q r=y
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=v
u Q r=y
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=x
u Q r=
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=y
u Q r=w
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=w
u Q r=z
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
t=z
u Q r=
x
BFS(G, u):
3. While Q ≠ Ø
v y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w z
Breadth-First Search (BFS)
u x BFS(G, u):
- the shortest-path
distance
v y from u
w z
Breadth-First Search (BFS)
u x BFS(G, u):
- the shortest-path
distance
v y from u
- construct a tree
w z
Breadth-First Search (BFS)
u x BFS(G, u):
- Initialization: |V|
- Enqueuing/dequeuing:
v y |V|
- Scanning adj vertices: |E|
w z
Breadth-First Search (BFS)
u x BFS(G, u):
- Initialization: O(|V|)
- Enqueuing/dequeuing:
v y O(|V|)
- Scanning adjacent
vertices:
O(|E|)
w z => total running time:
O(|V| + |E|)
BFS Algorithm
Step 1: SET STATUS = 1 (ready state) for each
node in G
Step 2: Enqueue the starting node A and set its
STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4: Dequeue a node N. Process it and set its
STATUS = 3 (processed state).
Step 5: Enqueue all the neighbours of N that are in
the ready state (whose STATUS = 1) and set their
STATUS = 2 (waiting state) [END OF LOOP]
Step 6: EXIT
Depth First Search
The step by step process to implement the DFS
traversal
1.First, create a stack with the total number of vertices in the
graph.
2.Now, choose any vertex as the starting point of traversal, and
push that vertex into the stack.
3.After that, push a non-visited vertex (adjacent to the vertex on
the top of the stack) to the top of the stack.
4.Now, repeat steps 3 and 4 until no vertices are left to visit from
the vertex on the stack's top.
5.If no vertex is left, go back and pop a vertex from the stack.
6.Repeat steps 2, 3, and 4 until the stack is empty.
Depth-First Search (DFS)
Applications of DFS algorithm
•DFS algorithm can be used to implement the
topological sorting.
•It can be used to find the paths between two
vertices.
•It can also be used to detect cycles in the graph.
•DFS algorithm is also used for one solution puzzles.
•DFS is used to determine if a graph is bipartite or
not.
Depth-First Search (DFS)
d[u]: when u is discovered
f[u]: when searching adj of u
u is finished
v w
Depth-First Search (DFS)
timestamp: t
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
v w
Depth-First Search (DFS)
timestamp: t+1
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
v w
d[v] = t+1
Depth-First Search (DFS)
timestamp: t+2
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
v w
d[v] = t+1
f[v] = t+2
Depth-First Search (DFS)
timestamp: t+3
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
v w
d[v] = t+1 d[w] = t+3
f[v] = t+2
Depth-First Search (DFS)
timestamp: t+4
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
v w
d[v] = t+1 d[w] = t+3
f[v] = t+2 f[v] = t+4
Depth-First Search (DFS)
timestamp: t+5
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
f[u] = t+5
v w
d[v] = t+1 d[w] = t+3
f[v] = t+2 f[w] = t+4
Depth-First Search (DFS)
d[u]: when u is discovered
f[u]: when searching adj of u
d[u] = t u is finished
f[u] = t+5
1. d[u] < f[u]
v w 2. [ d[u], f[u] ] entirely contains
d[v] = t+1 d[w] = t+3 [ d[v], f[v] ]
f[v] = t+2 f[w] = t+4 3. [ d[v], f[v] ] and [ d[w], f[w] ]
are entirely disjoint
Depth-First Search (DFS)
Not
u x discovered
Discovered,
adjacent
v y white nodes
Discovered,
no adjacent
w z white nodes
Depth-First Search (DFS)
Not
u x discovered
Discovered,
adjacent
v y white nodes
Discovered,
no adjacent
w z white nodes
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
for each u V[G],
color[u] white
v y
π[u] Nil
time 0
w z
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z color[u] gray
d[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. for each adj v of white
π[v] u
DFS-Visit[v]
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. for each adj v of white
π[v] u
DFS-Visit[v]
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. for each adj v of white
π[v] u
DFS-Visit[v]
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u x DFS(G):
- construct a forest
v y
w z
Depth-First Search (DFS)
u x DFS(G):
- Initialization: O(|V|)
- Traversing vertices: O(|V|)
v y - Scanning adjacent
vertices:
O(|E|)
=> total running time:
w z O(|V| + |E|)
Algorithm
Step 1: SET STATUS = 1 (ready state) for each
node in G
Step 2: Push the starting node A on the stack
and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is
empty
Step 4: Pop the top node N. Process it and set
its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbors of N
that are in the ready state (whose STATUS = 1)
and set their STATUS = 2 (waiting state)
[END OF LOOP]
Pseudocode
1.DFS(G,v) ( v is the vertex where the search starts )
2. Stack S := {}; ( start with an empty stack )
3. for each vertex u, set visited[u] := false;
4. push S, v;
5. while (S is not empty) do
6. u := pop S;
7. if (not visited[u]) then
8. visited[u] := true;
9. for each unvisited neighbour w of u
10. push S, w;
11. end if
12. end while
13. END DFS()
