Graph Search Methods
Graph Search Methods
A vertex u is reachable from vertex v iff there is a path from v to u.
A search method starts at a given vertex v and visits/labels/marks/prints every
vertex that is reachable from v.
1 2
3
8
4
5 9
10
6 11
7
Graph Search Methods
Many graph problems solved by a search method
– Finding a path from one vertex to another.
– Determining whether a graph is connected
– Find a spanning tree
– Finding a minimum-cost path/spanning tree
Commonly used search/traversal methods
– Breadth-first search (BFS)
– Depth-first search (DFS)
Breadth-First Search (BFS) Algorithm
BFS algorithm is the method of starting at a vertex and identifying all vertices
reachable from it
Similar to the level-order traversal (indirect level order traversal))of a binary tree
The queue(FIFO) data structure is used.
Breadth-First Search (BFS) Algorithm
Visit the starting vertex and put into a FIFO queue
Extra array called ‘visited’ ,is created and index of this array is each vertex
number, its size equal to total vertex number and its value is Boolean type. This
arrays keeps track of visited/print and un visited vertex.
This array index corresponding to the vertex is filled with initially “False” when
the vertex is not visited. Once visited make it “True”.
Repeatedly remove a vertex from the queue,
if(vis[curr]==F)
{ 1. print/visit current vertex.
2. make true in ‘visited’ array for the corresponding current vertex.
3. Add current vertex neighbors in queue. }
When the queue becomes empty, the search is terminated
Breadth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Start search at vertex 1.
Breadth-First Search Example
FIFO queue
1 2
3 1
8
4
5 9
10
6 11
7
Mark/label start vertex and put in a FIFO queue.
Remove 1 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Breadth-First Search Example
1 2
3 FIFO queue
8 24
4
5 9
10
6 11
7
Remove 2 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
1 2 FIFO queue
3
8
4536
4
5 9
10
6 11
7
Remove 4 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
2 FIFO queue
1 3 536
8
4
5 9
10
6 11
7
Remove 5 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
FIFO queue
1 2
3 3697
8
4
5 9
10
6 11
7
Remove 3 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
1 2 FIFO queue
3
8 697
4
5 9
10
6 11
7
Remove 6 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
2 FIFO queue
1 3 97
8
4
5 9
10
6 11
7
Remove 9 from Queue;
Visit adjacent unvisited vertices;
Put the visited vertices in Queue.
Are there any newly visited vertices?
Breadth-First Search Example
1 2 FIFO queue
3
8 78
4
5 9
10
6 11
7
Remove 7 from Queue;
Visit adjacent unvisited vertices;
Put in Queue.
Breadth-First Search Example
1 2 FIFO queue
3
8 8
4
5 9
10
6 11
7
Remove 8 from Queue;
Visit adjacent unvisited vertices;
Put in Queue.
Breadth-First Search Example
1 2
3 FIFO queue
8
4
5 9
10
6 11
7
Queue is empty, thus the search terminates.
Breadth-First Search Example
What was the order of visited vertices?
1, 2, 4, 3, 5, 6, 7,9, 8
Path Finding Problem from vertex u to vertex v
Start a breadth-first search at vertex u.
Terminate if either of the following occurs
– successfully when vertex v is visited or
– unsuccessfully when queue becomes empty but v is not visited
Is a Graph Connected?
Start a breadth-first search at any vertex of the graph.
A graph is connected iff all n vertices are visited.
Time
– O(n2) when adjacency matrix used
– O(n+e) when adjacency lists used
(e is number of edges)
Connected Components
Start a breadth-first search at any unvisited vertex of the graph.
Newly visited vertices (plus edges between them)
define a component.
Repeat until all vertices are visited.
Time
– O(n2) when adjacency matrix used
– O(n+e) when adjacency lists used
(e is number of edges)
Connected Components
1 2
3
8
4
5 9
10
6 11
7
Depth-First Search (DFS) Algorithm
DFS algorithm is an alternative to BFS
Similar to the pre-order traversal of a binary tree
Keep going to the first neighbor
Depth-First Search (DFS) Algorithm
Visit the starting vertex v and mark it as reached
Select an unreached first neighbor vertex u adjacent from v
If such a vertex does not exist, the search terminates,
otherwise a depth-first search from u is initiated
When this search is completed, we select another
unreached vertex adjacent to from v
If such a vertex does not exist, then the search terminates,
otherwise a depth-first search starts from this vertex
and so on…..
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Start search at vertex 1.
Label vertex 1 as reached and do a depth-first search
from either 2 or 4.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 2 and do a depth-first search
from either 3, 5 or 6.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 5 and do a depth-first search
from either 3, 7 or 9.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 9 and do a depth-first search
from either 6 or 8.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 8 and return to vertex 9.
From vertex 9 do a DFS(6).
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 6 and do a depth-first search
from either 4 or 7.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 4 and return to 6.
From vertex 6 do a DFS(7).
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label vertex 7 and return to 6.
Return to 9.
Depth-First Search Example
2
1
3
8
4
5 9
10
6 11
7
Return to 5.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Do a DFS(3).
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
Label 3 and return to 5.
Return to 2.
Return to 1.
Depth-First Search Example
1 2
3
8
4
5 9
10
6 11
7
DFS is done and return to invoking method.
Depth-First Search Example
What was the order of visited vertices?
1, 2, 5, 9, 8, 6, 4, 7, 3
Exercise
1 a) Draw a linked adjacency-list
28
2 representation
10
14 b) Starting from vertex 4, the order
16
of visited vertices using BFS are?
6 7 3
c) Show the subgraph formed in part
25 24 (b)
12
5
18 d) Redo parts (b) & (c) using DFS
22
4
Exercise – solution (a) & (b)
(a) Draw a linked adjacency- (b) Starting from vertex 4, the
list representation order of visited vertices are
4,3,5,7,2,6,1
Exercise – solution (c) & (d)
(c) Show the subgraph (d) Redo parts (b) & (c) using
formed in part (b) DFS
DFS order: 4,3,2,1,6,5,7
Properties of MST
a)It is a subgraph
b)All vertices are included
c)All vertices are connected
d)No cycles
e)Edge weight will be minimum . Therefore it is called MST.
f)Undirected
g)Connected and weighted
