1

SPD3255
Discrete Structures

Topic 6
~ Graphs (Part I)

Prepared by Dr. Desmond TSOI

School of Professional Education and Executive Development (SPEED)
College of Professional and Continuing Education (CPCE), The Hong Kong Polytechnic University

Lecture notes are based on textbook and various resources over the Internet
The use of this lecture note is solely for academic purpose and is subject to the approval of course instructor
 SPD3255 Discrete Structures

2 Graph Fundamentals
 Graphs
3

A graph is a way to represent

relationships between entities
Definition: Graph G

A graph G consists of a set of node / vertices,

denoted as V and a set of edges, denoted as E
• Number of nodes = |V| or n
• Number of edges = |E| or e

Two types of graphs:

Undirected graph
Directed graph / digraph

Undirected Graph Directed Graph

 Undirected Graph and Terminology
Definition: Undirected Graph a
G = (V, E)
4
An undirected graph is graph that are V = { a, b, c, d, e, f }
d
connected together, where all the b E = { (a,b), (a,d), (b,a), (b,d),
edges are bidirectional (b,e), (b,f), (b,c), (c,b),
c (c,e), (d,a), (d,b), (d,f),
f
Incident: (e,b), (e,c), (f,b), (f,d) }
e
An edge (x,y) incidents upon vertices x
and y
• Incident: The edge (a,b) incidents vertices a and b
Adjacent: • Adjacent: a, b are adjacent, a, d are adjacent, etc.
a and b are adjacent if (x,y) is an edge • Degree of node b: 5
in E node • Simple path: a, b, c
Degree of a node: • Cycle: a, b, d, a
Number of distinct edges incident
with it node
Simple path:
No vertex appears twice in the path
path node
Cycle:
A path in G contains at least 3
vertices, such that the last vertex in
the sequence is adjacent to the first
vertex in the sequence cycle => loop
 Undirected Graph and Terminology
Connected: a
5 A graph G is connected any two G = (V, E)
d V = { a, b, c, d, e, f }
vertices x and y in G has a path b
with first vertex x and last vertex y E = { (a,b), (a,d), (b,a), (b,d),
(b,e), (b,f), (b,c), (c,b),
Undirected complete graph: c f (c,e), (d,a), (d,b), (d,f),
An undirected graph G has an e (e,b), (e,c), (f,b), (f,d) }
edge between every pair of
• The graph is connected
vertices in G node node
• The graph is NOT complete, but the subgraph
Undirected cyclic graph: formed by node a,b,d is complete
An undirected graph with cycle • The graph is a cyclic undirected graph, since there
cycle
are cycle, e.g. c, b, e, c OR a, b, d, a, etc.
Undirected acyclic graph:
An undirected graph without cycle
cycle
Forest:
An acyclic graph whose connected
components are trees
 Directed Graph and Terminology
Definition: Undirected Graph a
6 G = (V, E)
A directed graph is graph that are connected d V = { a, b, c, d, e, f }
together, where all the edges are directed from b E = { (b,a), (b,e), (b,f),
one vertex to another (b,c), (d,a), (d,b),
c f (e,c), (f,d) }
In-degree of a vertex: e
Number of edges pointing into the node
• In-degree of node b: 1
Out-degree of a vertex: • Out-degree of node b: 4
Number of edges pointing out from the • Directed path from d to c: d b c OR
node d b e c
• Directed cycle: d b f d
Directed path:
Sequence of distinct nodes, such that
there is an edge from each vertex in the
sequence to the next
Directed cycle:
A directed path in G that the last vertex
in the sequence is pointing to the first
vertex in the sequence
 Directed Graph and Terminology
7 Connected: a
A graph G is connected any G = (V, E)
d
two vertices x and y in G has b V = { a, b, c, d, e, f }
a directed path with first E = { (b,a), (b,e), (b,f), (b,c),
vertex x and last vertex y c f (d,a), (d,b), (e,c), (f,d) }
Directed complete graph: e
A directed graph G has a
directed edge between every • The graph is NOT connected, since no path from e to a
• The graph is NOT complete, not every pair of vertices in
pair of vertices in G
G has directed edges, e.g. c and d
Directed cyclic graph: • The graph is a cyclic directed graph, since there are cycle,
A directed graph with e.g. b f d b.
directed cycle
Directed acyclic graph (DAG):
A directed graph without
directed cycle
 Weighted Graph
8

Definition: Weighted Graph

A weighted graph is a graph (can be either undirected / directed) associates a label

(weight) with every edge in the graph

Weights are usually real numbers

a a
5.2 11 20
10
3.1 7 d
d
20 b 21 b
-5 1.7 2.9 -1
9 c 4.2
c f f
e e
2.7 61.2

SPD3255 Discrete Structures

 Definition: Subgraph

Subgraph A subgraph, H, of a graph G is a graph whose vertices are a subset of

vertex set of G, and whose edges are a subset of the edge set of G
9

b a b a b a

b a b a b a

b a a b a

a b
 Graph Representations
10

Graphs can be represented

using one of the following
two representations
Adjacency matrix
Adjacency list

a b c d e f a b d NULL

a 1 1 0 1 0 0 b a d f e c NULL
b 1 1 1 1 1 1 c b e NULL
c 0 1 1 0 1 0
M d a b f NULL
d 1 1 0 1 0 1
e 0 1 1 0 1 0 e c b NULL
f 0 1 0 1 0 1 f b d NULL
Graph Representations – Adjacency Matrix
Suppose we have a graph
G = (V,E) with n or |V|
vertices, then an a a
adjacency matrix M is an n
d d
by n matrix defined as b b
follows:
c c f
f
1 if (i, j) is an edge e e
mij
0 otherwise
a b c d e f a b c d e f
a 1 1 0 1 0 0 a 0 0 0 0 0 0
b 1 1 1 1 1 1 b 1 0 1 0 1 1
c 0 1 1 0 1 0 c 0 0 0 0 0 0
M M
d 1 1 0 1 0 1 d 1 1 0 0 0 0
e 0 1 1 0 1 0 e 0 0 1 0 0 0
f 0 1 0 1 0 1 f 0 0 0 1 0 0
 Adjacency Matrix
12

Pros:
Easy to determine whether an edge
exist between any two nodes
Easy to add or remove an edge
Cons:
Require |V|2 or n2 space and memory
space is wasted if the graph is not
complete a b c d e f
Require |V| or n time to check whether a 1 1 0 1 0 0
all nodes could be reached by a specific b 1 1 1 1 1 1
node c 0 1 1 0 1 0
Difficult to add or remove a node M
d 1 1 0 1 0 1
If the graph is undirected, the matrix is e 0 1 1 0 1 0
symmetric which is again a waste of
memory f 0 1 0 1 0 1
 Graph Representations
– Adjacency List
13
An adjacency list is an array of linked lists
showing the adjacent nodes of every node
The following is an example of undirected
graph and its corresponding adjacency list:

a b d NULL

a b a d f e c NULL

d c e
b b NULL

d a b f NULL
c f
e e c b NULL

f b d NULL
 Graph Representations – Adjacency List
14
The following is an example of directed graph and its corresponding
adjacency list:

a NULL

a b a f e c NULL

d c NULL
b
d a b NULL
c f
e e c NULL

f d NULL
 Adjacency List
15

Pros:
Only require |V|+|E| or
n+e space
Require |V| or n for
finding all neighboring
nodes of a specific node
Cons:
Require |V| or n time to
determine if there a node
is connected to another
node
Require |V| or n time to
add or remove an edge
Difficult to add or remove
a node
 Graph Traversal
16

Traverse a graph means

Visit all the graph nodes / vertices
The order of visit depends on the traversal
algorithms
Traversal algorithms
Breath-First Search traversal (BFS)
Depth-First Search traversal (DFS)
 SPD3255 Discrete Structures

17 Breadth-First Search (BFS)

 Graph Traversal –
Breadth-First Search (BFS)
18

Idea:
Starting from a node S, visit the other
nodes / vertices at increasing distances
(i.e. number of edges) from S
Algorithm:
For each node / vertex v in graph, mark
every vertex as unvisited
Mark the start node S as visited
enqueue S to a queue Q
while(Q is NOT empty)
v = dequeue Q
for each w adjacent to v
if w is not visited
mark it to visited & enqueue it to Q
 Breadth-First Search - Example
19

Assume
Start from node a
Use adjacency list as
graph representation

a b d NULL
a b a d f e c NULL
d c
b b e NULL

d a b f NULL
c f
e e c b NULL

f b d NULL
 Breadth-First Search
– Example (Initial)
20
a

d Q={}
b
Order of visit:
c f
e

a b d NULL Visited Table

b a d f e c NULL a F
b F
c b e NULL
c F
d a b f NULL d F
e c b NULL e F
f b f F
d NULL
 Breadth-First Search
– Example (Step 1)
21

Q={a}
d
b
Order of visit: a
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b F
c b e NULL
c F
d a b f NULL d F
e c b NULL e F
f b f F
d NULL
 Breadth-First Search
– Example (Step 2)
22

Q = { b, d }
d
b
Order of visit: a
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c F
d a b f NULL d T
e c b NULL e F
f b f F
d NULL
 Breadth-First Search
– Example (Step 3)
23

Q = { d, f, e, c }
d
b
Order of visit: a, b
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c T
d a b f NULL d T
e c b NULL e T
f b f T
d NULL
 Breadth-First Search
– Example (Step 4)
24

Q = { f, e, c }
d
b
Order of visit: a, b, d
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c T
d a b f NULL d T
e c b NULL e T
f b f T
d NULL
 Breadth-First Search
– Example (Step 5)
25

Q = { e, c }
d
b
Order of visit: a, b, d, f
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c T
d a b f NULL d T
e c b NULL e T
f b f T
d NULL
 Breadth-First Search
– Example (Step 6)
26

Q={c }
d
b
Order of visit: a, b, d, f, e
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c T
d a b f NULL d T
e c b NULL e T
f b f T
d NULL
 Breadth-First Search
– Example (Step 7)
27

Q={ }
d
b
Order of visit: a, b, d, f, e, c
c f
e

a b d NULL Visited Table

b a d f e c NULL a T
b T
c b e NULL
c T
d a b f NULL d T
e c b NULL e T
f b f T
d NULL
 Shortest Path Finding using
28
Breadth-First Search (BFS)
The BFS introduced just now only let us know
whether a path exists from the source to other
nodes, but it doesn’t record the paths
We could slightly modify the algorithm to record to the path from
s to each node and the shortest path length
Algorithm:
For each node / vertex v in graph, mark every vertex as unvisited, set
all entries of predecessor array to NULL and distance array to infinity
Mark the start node S as visited and distance from s to 0
enqueue S to a queue Q
while(Q is NOT empty)
v = dequeue Q
for each w adjacent to v
if w is not visited, then
mark it to visited, set the predecessor to v, d(w) = d(v)+1 &
enqueue it to Q
 Breadth-First Search
- Example
29

Assume
Start from node a
Use adjacency list as graph representation

a b d NULL

a b a d f e c NULL

d c b e NULL
b
d a b f NULL
c f
e e c b NULL

f b d NULL
 Breadth-First Search
– Example (Initial)
30

Q={}
d
b
Order of visit:
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a F a NULL ∞
b a d f e c NULL
b F b NULL ∞
c b e NULL c F c NULL ∞

d a b f NULL d F d NULL ∞

e e F e NULL ∞
c b NULL
f F f NULL ∞
f b d NULL
 Breadth-First Search
– Example (Step 1)
31

Q={a}
d
b
Order of visit: a
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b F b NULL ∞
c b e NULL c F c NULL ∞

d a b f NULL d F d NULL ∞

e e F e NULL ∞
c b NULL
f F f NULL ∞
f b d NULL
 Breadth-First Search
– Example (Step 2)
32

Q = { b, d }
d
b
Order of visit: a
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c F c NULL ∞

d a b f NULL d T d a 1

e e F e NULL ∞
c b NULL
f F f NULL ∞
f b d NULL
 Breadth-First Search
– Example (Step 3)
33

Q = { d, f, e, c }
d
b
Order of visit: a, b
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c T c b 2

d a b f NULL d T d a 1

e e T e b 2
c b NULL
f T f b 2
f b d NULL
 Breadth-First Search
– Example (Step 4)
34

Q = { f, e, c }
d
b
Order of visit: a, b, d
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c T c b 2

d a b f NULL d T d a 1

e e T e b 2
c b NULL
f T f b 2
f b d NULL
 Breadth-First Search
– Example (Step 5)
35

Q = { e, c }
d
b
Order of visit: a, b, d, f
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c T c b 2

d a b f NULL d T d a 1

e e T e b 2
c b NULL
f T f b 2
f b d NULL
 Breadth-First Search
– Example (Step 6)
36

Q={c }
d
b
Order of visit: a, b, d, f, e
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c T c b 2

d a b f NULL d T d a 1

e e T e b 2
c b NULL
f T f b 2
f b d NULL
 Breadth-First Search
– Example (Step 7)
37

Q={ }
d
b
Order of visit: a, b, d, f, e, c
c f
e
Predecessor and
Visited Table distance table
a b d NULL
a T a NULL 0
b a d f e c NULL
b T b a 1
c b e NULL c T c b 2

d a b f NULL d T d a 1

e e T e b 2
c b NULL
f T f b 2
f b d NULL
 Paths from Source to Each Node
38

Algorithm:
Path(w) a

If predecessor[w] is not NULL d Predecessor and

Path(predecessor[w]) b
distance table
Output w 0
c f
a NULL

e b a 1

c b 2
a
d a 1
1 1 e b 2
b d
f b 2
2 c f
2
e
2
BFS Tree
 SPD3255 Discrete Structures

39 Depth-First Search (DFS)

 Graph Traversal –
Depth-First Search (DFS)
40

Idea:
Similar to pre-order traversal of tree in which visit children node first
Continue visit neighbors in a recursive manner,
i.e. if we visit v from u, we recursively visit all unvisited neighbors of v and then
return back to u
Algorithm:
DFS(s)
for each node v
set it to unvisited
RDFS(s);
RDFS(v)
mark v as visited
for each neighbor node w of v
if w is unvisited, RDFS(w)
 Depth-First Search - Example
41

Assume
Start from node a
Use adjacency list as
graph representation

a b d NULL
a
b a d f e c NULL
d
b c b e NULL

c d a b f NULL
f
e e c b NULL

f b d NULL
 Depth-First Search
– Example (Initial)
42

d
b
Order of visit:
c f
e
Predecessor
Visited Table table
a b d NULL
a F a NULL
b a d f e c NULL
b F b NULL

c b e NULL c F c NULL

d a b f NULL d F d NULL

e e F e NULL
c b NULL
f F f NULL
f b d NULL
 Depth-First Search
– Example (Step 1)
43
(1
a

d
b
Order of visit:
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b F b NULL

c b e NULL c F c NULL

d a b f NULL d F d NULL

e e F e NULL
c b NULL
f F f NULL
f b d NULL
 Depth-First Search
– Example (Step 2)
44
(1
a
(2
d
b
Order of visit:
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d F d NULL

e e F e NULL
c b NULL
f F f NULL
f b d NULL
 Depth-First Search
– Example (Step 3)
45
(1
a
(3
(2
d
b
Order of visit:
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d T d b

e e F e NULL
c b NULL
f F f NULL
f b d NULL
 Depth-First Search
– Example (Step 4)
46
(1
a
(3
(2
d
b
Order of visit:
(4
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d T d b

e e F e NULL
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 5)
47
(1
a
(3
(2
d
b
Order of visit: f
(4,5)
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d T d b

e e F e NULL
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 6)
48
(1
a
(3,6)
(2
d
b
Order of visit: f, d
(4,5)
c f
e
Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d T d b

e e F e NULL
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 7)
49
(1
a
(3,6)
(2
d
b
Order of visit: f, d
(4,5)
c f
e
(7 Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c F c NULL

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 8)
50
(1
a
(3,6)
(2
d
b
Order of visit: f, d
(4,5)
c f
(8 e
(7 Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c T c e

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 9)
51
(1
a
(3,6)
(2
d
b
Order of visit: f, d, c
(4,5)
c f
(8,9) e
(7 Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c T c e

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 10)
52
(1
a
(3,6)
(2
d
b
Order of visit: f, d, c, e
(4,5)
c f
(8,9) e
(7,10) Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c T c e

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 11)
53
(1
a
(3,6)
(2,11)
d
b
Order of visit: f, d, c, e, b
(4,5)
c f
(8,9) e
(7,10) Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c T c e

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Depth-First Search
– Example (Step 12)
54
(1,12)
a
(3,6)
(2,11)
d
b

(4,5)
c f Order of visit: f, d, c, e, b, a
(8,9) e
(7,10) Predecessor
Visited Table table
a b d NULL
a T a NULL
b a d f e c NULL
b T b a

c b e NULL c T c e

d a b f NULL d T d b

e e T e b
c b NULL
f T f d
f b d NULL
 Paths from Source to Each Node
55

Algorithm:
Path(w) a
If predecessor[w] is not NULL
d
Path(predecessor[w]) b
Output w Predecessor
c f table
e
a NULL

b a
a
c e

b d d b

e b
c f
e f d

DFS Tree
 Final Note about BFS and DFS
56

The order of BFS or DFS

traversal depends on the
adjacency list
Different adjacent list
representations of graph will
give different traversal order
Adjacency matrix could also be
used as graph representation
for BFS and DFS
 Further Reading
57

Read Chapter 10 of “Discrete Mathematics with

Applications” textbook

SPD3255 Discrete Structures