0% found this document useful (0 votes)

3 views50 pages

Graph Searching

The document discusses graph searching techniques, specifically focusing on Breadth-First Search (BFS) and Depth-First Search (DFS). It explains how BFS explores a graph layer by layer to build a breadth-first tree, while DFS explores deeper into the graph, distinguishing between different types of edges. Both algorithms have their own properties and applications, including calculating shortest paths and identifying tree structures within graphs.

Uploaded by

sattwiksaha888

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

3 views50 pages

Graph Searching

Uploaded by

sattwiksaha888

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Graphs (Cont.

graph (many to many)

1
Graph Searching
• Given: a graph G = (V, E), directed or undirected
• Goal: methodically explore every vertex and every edge
• Ultimately: build a tree on the graph
– Pick a vertex as the root
– Choose certain edges to produce a tree
– Note: might also build a forest if graph is not connected

• There are two standard graph traversal techniques:

▪ Breadth-First Search (BFS)
▪ Depth-First Search (DFS)
Breadth-First Search
• “Explore” a graph, turning it into a tree
– One vertex at a time
– Expand frontier of explored vertices across the
breadth of the frontier
• Builds a tree over the graph
– Pick a source vertex to be the root
– Find (“discover”) its children, then their children,
etc.
Breadth-First Search
• Again will associate vertex “colors” to guide
the algorithm
– White vertices have not been discovered
• All vertices start out white
– Grey vertices are discovered but not fully explored
• They may be adjacent to white vertices
– Black vertices are discovered and fully explored
• They are adjacent only to black and grey vertices
• Explore vertices by scanning adjacency list of
grey vertices
Breadth-First Search
Breadth-First Search: Example
r s t u

   

   
v w x y
Breadth-First Search: Example
r s t u

 0  

   
v w x y

Q: s
Breadth-First Search: Example
r s t u

1 0  

 1  
v w x y

Q: w r
Breadth-First Search: Example
r s t u

1 0 2 

 1 2 
v w x y

Q: r t x
Breadth-First Search: Example
r s t u

1 0 2 

2 1 2 
v w x y

Q: t x v
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 
v w x y

Q: x v u
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: v u y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: u y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: y
Breadth-First Search: Example
r s t u

1 0 2 3

2 1 2 3
v w x y

Q: Ø
BFS - A Graphical Representation
0 0 1

A B C D A B C D

a) b)
E F G H E F G H

I J K L I J K L

M N O P M N O P
0 1 2
0 1 2 3
A B C D A B C D
c) d)
E F G H E F G H

I J K L
I J K L

M N O P
M N O P
BFS - A Graphical Representation

e) f)
0 1 2 3 0 1 2 3

A B C D A B C D

E F G H E F G H

4 4
I J K L I J K L

M N O P M N O P 5
BFS: The Code Again
BFS(G, s) {
initialize vertices; Touch every vertex: O(V)
Q = {s};
while (Q not empty) {
u = RemoveTop(Q);
for each v  u->adj {
u = every vertex, but only once
if (v->color == WHITE)
(Why?)
v->color = GREY;
So v = every vertex thatv->d = u->d + 1;
appears in some other v->p = u;
vert’s adjacency list Enqueue(Q, v);
}
u->color = BLACK;
}
} What will be the running time?
Total running time: O(V+E)
BFS: The Code Again
BFS(G, s) {
initialize vertices;
Q = {s};
while (Q not empty) {
u = RemoveTop(Q);
for each v  u->adj {
if (v->color == WHITE)
v->color = GREY;
v->d = u->d + 1;
v->p = u;
Enqueue(Q, v);
}
u->color = BLACK;
What will be the storage cost
}
in addition to storing the tree?
}
Total space used:
O(V + Σ(degree(v))) = O(V+E)
Breadth-First Search: Properties
• BFS calculates the shortest-path distance to
the source node
– Shortest-path distance (s,v) = minimum number
of edges from s to v, or  if v not reachable from s
• BFS builds breadth-first tree, in which paths to
root represent shortest paths in G
– Thus can use BFS to calculate shortest path from
one vertex to another in O(V+E) time in an
unweighted tree
Depth-First Search
• Depth-first search is another strategy for exploring a graph
– Explore “deeper” in the graph whenever possible
– Edges are explored out of the most recently discovered vertex v that still
has unexplored edges
– When all of v’s edges have been explored, backtrack to the vertex from
which v was discovered

Vertices initially colored white

Then colored grey when discovered
Then black when finished
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{
{
u->color = GREY;
for each vertex u  G->V time = time+1;
{ u->d = time;
u->color = WHITE; for each v  u->Adj[]
} {
time = 0; if (v->color == WHITE)
DFS_Visit(v);
for each vertex u  G->V
}
{
u->color = BLACK;
if (u->color == WHITE) time = time+1;
DFS_Visit(u); u->f = time;
} }
}
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{
{
u->color = GREY;
for each vertex u  G->V time = time+1;
{ u->d = time;
u->color = WHITE; for each v  u->Adj[]
} {
time = 0; if (v->color == WHITE)
DFS_Visit(v);
for each vertex u  G->V
}
{
u->color = BLACK;
if (u->color == WHITE) time = time+1;
DFS_Visit(u); u->f = time;
} }
}

What does u->d represent?

Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{
{
u->color = GREY;
for each vertex u  G->V time = time+1;
{ u->d = time;
u->color = WHITE; for each v  u->Adj[]
} {
time = 0; if (v->color == WHITE)
DFS_Visit(v);
for each vertex u  G->V
}
{
u->color = BLACK;
if (u->color == WHITE) time = time+1;
DFS_Visit(u); u->f = time;
} }
}

What does u->f represent?

DFS Example
source
vertex
DFS Example
source
vertex
d f

1 | | |

| |

| | |
DFS Example
source
vertex
d f

1 | | |

2 | |

| | |
DFS Example
source
vertex
d f

1 | | |

2 | |

3 | | |
DFS Example
source
vertex
d f

1 | | |

2 | |

3 | 4 | |
DFS Example
source
vertex
d f

1 | | |

2 | |

3 | 4 5 | |
DFS Example
source
vertex
d f

1 | | |

2 | |