Graph
Prof. Dipak Patel, VGEC-IT, Ahmedabad
Graphs:Review
● A graph
■ A graph G consists of a nonempty set V called the set of
nodes (points or vertices) of the graph and set E which is
set of edges of the graph and a mapping from the set of
edges E to a set of pairs of elements of V.
■ Denoted by G = (V, E)
○ V = set of vertices, E = set of edges
■ Dense graph: |E| ≈ |V|2; Sparse graph: |E| ≈ |V|
Basic Types of Graph
● Directed graph:
■ If every edge (i,j) in E(G) of
graph G is marked by a
direction from i to j then the
graph is called directed graph.
It is also called digraph.
● Undirected graph:
■ A graph in which every edge is
undirected is called undirected
graph. i.e. the edges are
bidirectional.
■ edge (u,v) = edge (v,u)
Basic Types of Graph
● A weighted graph associates weights with either the
edges or the vertices
1 2
3 1
2 3
2 1
4
Graph Terminology
● The degree of a vertex in an undirected graph is the
number of edges that leave/enter the vertex.
● The degree of a vertex in a directed graph is the
same, but we distinguish between in-degree and out-
degree. Degree = in-degree + out-degree.
Representing Graphs
● Adjacency-Matrix
■ Consider Graph G(V,E) and Assume V = {1, 2, …, n}
■ An adjacency matrix represents the graph as a n x n matrix A:
■ A[i, j] = 1 if edge (i, j) ∈ E (or weight of edge)
= 0 if edge (i, j) ∉ E
1 2 3 4 5
1 0 1 1 0 0
2 0 0 0 0 0
3 0 0 0 1 0
4 1 0 0 0 0
5 0 1 0 1 0
Representing Graphs
● Adjacency-Matrix
1 2 3 4 5
1 0 1 1 1 0
2 1 0 0 0 1
3 1 0 0 1 0
4 1 0 1 0 1
5 0 1 0 1 0
■ Storage requirements: Ө(V2)
○ Efficient if a graph is dense
○ Undirected graph: only need to store upper or lower
triangular matrix
Representing Graphs
● Adjacency-List
■ There is a one list for each node (vertex) of graph G and each
list contains adjacent nodes.
1 2 3 \
2 \
3 4 \
4 1 \
5 2 4 \
■ If G is directed graph, the sum of length of all adjacency lists is
|E| and for undirected graph it’s 2|E|.
■ Amount of memory requires(for directed or undirected) is
Ө (V + E)
Representing Graphs
● Adjacency-List
1 2 3 4 \
2 1 5 \
3 1 4 \
4 1 3 5 \
5 2 4 \
■ If G is undirected graph, the sum of length of all adjacency lists
is 2|E|.
■ Amount of memory requires(for directed or undirected) is
Ө (V + E)
Representing Graphs
● Summary
■ Adjacency matrix representation takes Ө(V2) regardless of
number of edges in the graph.
■ Whereas space requirement for Adjacency list representation
is Ө (V + E)
■ It is easy to find all vertices adjacent to a given vertex in an
adjacency list representation. Simply read its adjacency list.
■ With an adjacency matrix you must instead scan over an
entire row.
■ How ever it’s easy to determine edge between two vertices
with adjacency matrix.
■ Whereas adjacency list requires time proportional to the
number of edges associated with the two vertices.
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
Breadth-First Search
● “Explore” a graph, turning it into a tree
■ The order of search is across levels.
■ The root is examined first; then children of the root ; then
children of nodes visited in first phase. etc…
Breadth-First Search
● we 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 gray vertices
● Explore vertices by scanning adjacency list of grey
vertices
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: The Code
BFS(G, s) {
initialize vertices; Touch every vertex: O(V)
Q = {s};
while (Q not empty) {
u = RemoveTop(Q); u = every vertex, but only once
for each v ∈ u->adj {
if (v->color == WHITE)
So v = every vertex v->color = GREY;
that appears in v->d = u->d + 1;
some other vert’s v->p = u;
adjacency list Enqueue(Q, v);
}
u->color = BLACK; What will be the running time?
} Total running time: O(V+E)
}
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
Depth-First Search
● Vertices initially colored white
● Then colored gray when discovered
● Then black when finished
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
What does u->d represent?
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
What does u->f represent?
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
Will all vertices eventually be colored black?
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
What will be the running time?
Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{ {
for each vertex u ∈ G->V u->color = GREY;
time = time+1;
{
u->d = time;
u->color = WHITE;
for each v ∈ u->Adj[]
}
{
time = 0;
if (v->color == WHITE)
for each vertex u ∈ G->V
DFS_Visit(v);
{
}
if (u->color == WHITE)
u->color = BLACK;
DFS_Visit(u);
time = time+1;
}
u->f = time;
}
}
So, running time of DFS = O(V+E)
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 | |
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |
3 | 4 5 | 6 |
What is the structure of the grey vertices?
What do they represent?
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |10
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 | 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 |12 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 |
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|15
DFS Example
source
vertex
d f
1 |12 8 |11 13|16
2 | 7 9 |10
3 | 4 5 | 6 14|15
