CSE-101 Lecture 27-30
Graphs
28, 29 October 2024
4, 5 November 2024
Graphs
• A non linear data structure that consists of a set of nodes and a
set of edges that connects the nodes.
• G(V,E) consists of:
1. A set V of elements called nodes (or points or vertices)
2. A set E of edges such that each edge e in E is identified with a unique
(unordered) pair [u,v] of nodes in V, denoted by e = [u, v]
Example:
Applications:
• Car Navigation System ( e.g. Google maps)
Vertices = intersection of roads , Edge = road
• Social Graphs (e.g. Facebook)
Vertices = users, Edge = friendship
• World Wide Web
Vertices = web pages, Edge = link between pages
• Communication Network
Vertices = city, Edge = communication link
• Many more ..
Graph Terminology
• e = [a,b], then a and b are called the endpoints of e
• a, b are said to be adjacent nodes or neighbors
• The degree of a node u, deg(u), is the number of edges containing u
eg. deg(c) = 3
• If deg(u) = 0, then u is called an isolated node
eg. node e
Terminology: Path
• A path P of length n from a node u to a node v is defined as a sequence of n+1
nodes.
P = (v0, v1 , v2 ,……vn)
such that u = v0 ,
vi-1 adjacent to vi for i = 1,2,…n
vn= v
abedc bedc
Terminology (contd..)
• The path P is said to be closed if v0 = vn
• The path P is said to be simple if all the nodes are distinct, with the exception
that v0 may equal vn
bec
• A cycle is a closed simple path with length 3 or more.
acda
• A cycle of length k is called a k-cycle.
Terminology (contd..)
• A graph G is said to be labeled if its edges are assigned data.
• G is said to be weighted if each edge e in G is assigned a nonnegative numerical value w(e) called the
weight or length of e.
• Each path P in G is assigned a weight or length which is the sum of the weights of the edges along the
path P.
From node B to node D
Path P1 = (B,C,D)
w(P1) = 10
Path P2 = (B,A,E,D)
w(P2) = 9
• If we are given no other information about weights, we may assume the weight w(e) = 1 to each edge e
in G.
Directed and Undirected Graph
• A Directed Graph (also called a digraph or graph) is the one in which
each edge e in G is assigned a direction.
V = {A, B, C, D, E}
E = {(A,B), (B,C), (C,B), (A,C), (A,E), (C,D)}
Directed Graph (contd..)
• Each edge e is identified with an ordered pair (u, v)
• e begins at u and ends at v.
• u - origin or initial point
v - destination or terminal point
• e - an out-edge of u and an in-edge of v
• u - predecessor of v
v - successor of u.
• u is adjacent to v and v is adjacent from u
• Edge e is incident on u and v
Directed Graph (contd..)
• The outdegree of a node u in G written outdeg(u), is the number of
edges beginning at u.
• The indegree of u, written indeg(u), is the number of edges ending at
u.
• A node v is said to be reachable from a node u if there is a (directed)
path from u to v.
Directed Graph (contd..)
• Tree and Graph Relation?
• There is a unique simple path rom the root to any other node in a tree.
Connectivity
• A graph G is said to be connected if there is a path between any two of its
node
Connected Not connected
• Subgraph: subset of vertices and edges forming a graph.
Let G=(V,E) and G’= (V’, E’)
G’ G iff V’ V and E’ E
Connectivity (contd..)
• If T is a tree with n nodes, then T will have n-1 edges
n =5
Total no. of edges = n -1 = 4
• If number of edges < n - 1, then G is not connected
n=5
No. of edges = 3 < (5 – 1)
Graph Representation
• There are two ways to store a graph in the memory:
• Sequential representation
– Adjacency Matrix
• Linked representation
– Adjacency Lists
Adjacency Matrix
• Let G is a simple directed graph with n nodes,
• The adjacency matrix A = (aij) of the graph G is the n x n matrix such that :
A(i,j) = 1, iff (i,j) is an edge
= 0, otherwise
Example:
P Q R S T
P 0 1 0 1 0
Q 1 0 1 0 0
R 0 1 0 1 0
S 1 0 1 0 1
T 0 0 0 1 0
Adjacency Matrix of Directed Graph
X Y Z W
X 0 0 0 1
Y 1 0 1 1
Z 1 0 0 1
W 0 0 1 0
Properties of Adjacency Matrix
• Matrix which includes only 0 and 1, is a Boolean matrix.
• Diagonal elements = 0.
• Space complexity = O(n2)
• For an undirected graph, the adjacency matrix will be a symmetric matrix.
that is, aij = aji for every i and j
Hence, only upper or lower triangle may be stored, n(n-1)/2 bits (excluding
diagonal)
Properties of Adjacency Matrix (contd..)
• For a directed graph, the adjacency matrix need not be symmetric.
• Time complexity = O(n), to find degree of any vertex
• Easy to implement and random access possible.
• Not suitable for sparse graph as matrix takes O(n2) in memory
Adjacency List
• Each node in graph is followed by a list of adjacent nodes, also called its
successors or neighbors.
• Adjacency list requires space for existing edges only.
• Example:
Adjacency List (contd..)
• Size of one dimensional array of linked list = n
• Each adjacency list is a chain.
• For directed graphs,
No. of chain nodes in adjacency lists is Σout-degree(v) = |e|
• For undirected graphs,
No. of chain nodes in adjacency lists is Σ degree(v) = 2|e|
• So Adjacency lists’ space complexity is O(n + e).
Graph Traversal
• Traversing a graph means visiting all nodes exactly once.
• There are two standard ways to traverse:
• Breadth First Search (BFS)
• Depth First Search (DFS)
Breadth-First Search (BFS)
Depth-First Search (DFS)
Breadth-First Search (BFS)
Not
u x white discovered
0 ∞
Discovered,
gray adjacent
v ∞ y
∞ white nodes
Discovered,
black no adjacent
w z white nodes
∞ ∞
Breadth-First Search (BFS)
u 0 ∞ x
BFS(G, u):
1. Initialize the graph
v ∞ y color[u] gray
∞
π[u] Nil
d[u] 0
for each other vertex
w ∞ ∞ z color[u] white
Breadth-First Search (BFS)
u 0 ∞ x Q u
BFS(G, u):
2. Initialize the queue
v ∞ y QØ
∞
Enqueue(Q, u)
w ∞ ∞ z
Breadth-First Search (BFS)
t=u
u 0 ∞ x Q
BFS(G, u):
3. While Q ≠ Ø
v ∞ y 1) t Dequeue(Q)
∞
w ∞ ∞ z
Breadth-First Search (BFS)
t=u
u Q v x r = x, v
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 ∞ 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 v x r = x, v
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 ∞ y 3) color[t] black
w ∞ ∞ z
Breadth-First Search (BFS)
t=v
u 0 1 x Q x
BFS(G, u):
3. While Q ≠ Ø
v 1 ∞ 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 x y r=y
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 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 x y r=y
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 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 y r=
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 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 w r=w
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w 3 ∞ z
Breadth-First Search (BFS)
t=w
u Q z r=z
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w 3 4 z
Breadth-First Search (BFS)
t=z
u Q r=∅
0 1 x
BFS(G, u):
3. While Q ≠ Ø
v 1 2 y 1) t Dequeue(Q)
2) for each r adj to t
…
3) color[t] black
w 3 4 z
Breadth-First Search (BFS) BFS(G, u):
1. Initialize the graph
color[u] gray
π[u] Nil
d[u] 0
for each other vertex
color[u] white
u 0 1 x 2. Initialize the queue
QØ
Enqueue(Q, u)
3. While Q ≠ Ø
v 1 2 y 1) t Dequeue(Q)
2) for each r adj to t
if color[r] = white
color[r] gray
π[r] t
w 3 4 z d[r] d[t] + 1
Enqueue(Q, r)
3) color[t] black
Breadth-First Search (BFS)
Breadth First Tree BFS:
- the shortest-path distance from u
- construct a tree
u 0 1 x
Complexity?
v 1 2 y
w 3 4 z
Breadth-First Search (BFS)
Breadth First Tree BFS:
- the shortest-path distance from u
- construct a tree
u 0 1 x
Complexity
BFS(G, u):
v 1 2 y - Initialization: O(|V|)
- Enqueuing/dequeuing: O(|V|)
- Scanning adjacent vertices: O(|E|)
w 3 4 z => total running time: O(|V| + |E|)
Depth-First Search (DFS)
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
f[u] = t+5 is finished
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
f[u] = t+5 is finished
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
Depth-First Search (DFS)
Not
u x white discovered
Discovered,
gray adjacent
v y white nodes
Discovered,
black no adjacent
w z white nodes
Depth-First Search (DFS)
Not
u x discovered
Discovered,
d/ adjacent
v y white nodes
Discovered,
d/f 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 1/ 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 1/ x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/
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 1/ x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/ 3/ 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 1/ 4/ x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/ 3/ 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 1/ 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/ 3/ 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 1/ 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/ 3/6 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 1/ 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 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 1/8 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 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 1/8 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w 9/ z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u 1/8 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w 9/ 10/ z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u 1/8 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w 9/ 10/11 z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
u 1/8 4/5 x DFS(G):
1. Initialization
2. For each u V[G]
if color[u] = white
v 2/7 3/6 y
DFS-Visit(u)
DFS-Visit(u):
1. Initial Setting
w 9/12 10/11 z 2. Handling adj vertices
3. color[u] black
f[u] time time + 1
Depth-First Search (DFS)
Depth First Forest
u 1/8 4/5 x
v 2/7 3/6 y
w 9/12 10/11 z
Depth-First Search (DFS)
DFS-Visit(u):
DFS(G): 1. Initial Setting:
1. Initialization: color[u] gray
for each u V[G]: d[u] time time + 1
color[u] white
π[u] Nil 2. Handling adj vertices:
time 0 π[v] u
2. For each u V[G] DFS-Visit(v)
if color[u] = white
DFS-Visit(u) 3. color[u] black
f[u] time time + 1
Complexity?
Depth-First Search (DFS)
Complexity
u 1/8 4/5 x DFS(G):
- construct a forest
- Initialization: O(|V|)
v 2/7 3/6 y - Traversing vertices: O(|V|)
- Scanning adjacent vertices: O(|E|)
=> total running time: O(|V| + |E|)
w 9/12 10/11 z
Properties of DFS
• Using DFT, we can verify if given graph contain cycle or not.
• Paths discovered by DFS are not shortest paths, unlike BFS.
