CS311

Algorithm Design and

Analysis
LECTURE 9 : GRAPH ALGORITHMS (1)
Contents
▪ Graph Definitions
▪ Graph Representations
▪ Breadth-first search
▪ Depth-first search
▪Minimum Spanning Tree
▪Kruskal’s Algorithm
▪Prim’s Algorithm
▪Kruskal’s Algorithm Versus Prim’s Algorithm

ALGORITHM DESIGN AND ANALYSIS 2

Data Structures
Linear Non-Linear

Tree

Array

Linked List

Graph
Stack Queue

ALGORITHM DESIGN AND ANALYSIS 3

Graph – Definitions
Graph – mathematical object consisting of a set of:
▪ Denoted by
▪ V = nodes (vertices, points).
▪ E = edges (links, arcs) between pairs of nodes,
Where each edge is a pair (v,w) s.t. v,w  V

ALGORITHM DESIGN AND ANALYSIS 4

Graphs - Definitions
▪ If the edge pair is ordered then the graph is called a directed graph (digraphs).
▪ Undirected graph, which is not a directed graph (normal graph or just a graph).
Undirected graph Directed graph

V = { A,B,C,D } V = { 1, 3,5,7,9,11}
E = {(A,B), (A,D), (B,D), (B,C)} E = {(1,3) (3,1) (11,1) (9,11) (9,9) (5,9) (5,7) }

ALGORITHM DESIGN AND ANALYSIS 5

Graphs - Definitions
We can label the edges of a graph with numeric values, the graph is called a weighted graph.
8
1 2
10 3 6
Weighted (Undirected) Graph
5 7
3 4 5

8
1 2
6 Weighted Directed Graph
10 3
5 7
3 4 5

6
Graphs - Definitions
▪ A connected graph has a path between each pair of distinct vertices.

▪ A complete graph has an edge between each pair of distinct vertices.

◦ A complete graph is also a connected graph. But a connected graph may not be a
complete graph.

connected disconnected complete

ALGORITHM DESIGN AND ANALYSIS 7

Graphs – Definitions
In graph, degree is the number of edges incident on a node
In digraph, Degree = in-degree + out-degree
• In-degree: Number of edges entering
• Out-degree: Number of edges leaving
outdeg(1)=2
indeg(1)=0

outdeg(2)=2
deg(1) = 2 indeg(2)=2
deg(2) = 3
deg(5) = 3 outdeg(3)=1
indeg(3)=4

ALGORITHM DESIGN AND ANALYSIS 8

Graphs - Definitions
Two vertices of a graph are adjacent if they are joined by an edge.
Vertex w is adjacent to v iff edge (v,w)  E.

Ex:
• 3 is adjacent to 1 ➔ (1,3)
From Edge (B,D) • 1 is adjacent to 3 ➔ (3,1)
. B is adjacent to D • 1 is adjacent to 11➔(11,1)
. D is adjacent to B.

ALGORITHM DESIGN AND ANALYSIS 9

Graphs - Definitions
▪ Path (Directed path) between two vertices is a sequence of edges that begins at one
vertex and ends at another vertex.

▪ Simple path: passes through a vertex only once.

▪ Cycle: is a path that begins and ends at the same vertex.

▪ Directed acyclic graph (DAG): is a type of directed graph having no cycles.

▪ Simple cycle is a cycle that does not pass through other vertices more than once.

ALGORITHM DESIGN AND ANALYSIS 10

 Graph – An Example
1 2

3 4 5

The graph G= (V,E) has 5 vertices and 6 edges:

V = {1,2,3,4,5}
E = { (1,2),(1,3),(1,4),(2,5),(3,4),(4,5), (2,1),(3,1),(4,1),(5,2),(4,3),(5,4) }

• Adjacent: 1 and 2 are adjacent , 1 is adjacent to 2 and 2 is adjacent to 1

• Path: 1,2,5 ( a simple path), 1,3,4,1,2,5 (a path but not a simple path)
• Cycle: 2,5,4,1,2 (a simple cycle), 1,3,4,1,4,1 (a cycle, but not simple cycle)
11
Directed Graph – An Example
1 2

3 4 5

The graph G= (V,E) has 5 vertices and 6 edges:

V = {1,2,3,4,5}
E = { (1,2),(1,4),(2,5),(4,5),(3,1),(4,3),(5,5) }

• Adjacent: 2 is adjacent to 1, but 1 is NOT adjacent to 2

• Path: 1,2,5 ( a directed path),
• Cycle: 1,4,3,1 (a directed cycle), 5,5 (a Self loop)

12
Graph Representations
You can choose between two standard ways to represent a graph G = (V, E) :
1. Adjacency lists.
2. Adjacency matrix.
Undirected graph

Adjacency list Adjacency matrix

For weighted graph: Weights are stored in adjacency lists Weights are stored instead of 1 and 0

ALGORITHM DESIGN AND ANALYSIS 13

Graph Representations
You can choose between two standard ways to represent a graph G = (V, E) :
1. Adjacency lists.
2. Adjacency matrix.
Directed graph

Adjacency list Adjacency matrix

For weighted graph: Weights are stored in adjacency lists Weights are stored instead of 1 and 0

ALGORITHM DESIGN AND ANALYSIS 14

Adjacency List Time and Space Complexity
For directed graphs:
◦ Sum of lengths of all adj. lists is
out-degree(v) = |E|
vV

For undirected graphs:

◦ Sum of lengths of all adj. lists is
degree(v) = 2|E|
vV

◦ Total storage for directed and undirected graph = (V+E)

◦ Time complexity: Finding each edge in the graph also takes (V+E) time

ALGORITHM DESIGN AND ANALYSIS 15

Adjacency Matrix Time and Space Complexity
Total storage for directed and undirected graph = (V2).
Time complexity:
▪ To list all vertices adjacent to u = (V).
▪ To determine if (u, v)  E = (1).

ALGORITHM DESIGN AND ANALYSIS 16

Breadth-first search
▪ One of the simplest algorithms for searching a graph and the archetype for many important
graph algorithms.

▪ Given a graph G =(V, E) and a distinguished source vertex s , BFS systematically explores
the edges of G to discover every vertex that is reachable from s.

▪ It computes the distance from s to each reachable vertex, where

the distance to a vertex v equals the smallest number of edges
needed to go from s to v .

▪ The algorithm works on both directed and undirected graphs.

ALGORITHM DESIGN AND ANALYSIS 17

Breadth-first search

ALGORITHM DESIGN AND ANALYSIS 18

BFS - Example
V d π
S 0 NIL
R  NIL
V  NIL
U  NIL
W  NIL
T  NIL
Y  NIL
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 19

BFS - Example
s V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W  NIL
T  NIL
Y  NIL
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 20

BFS - Example
r V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y  NIL
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 21

BFS - Example
u V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 22

BFS - Example
v V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 23

BFS - Example
t V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X  NIL
Z  NIL

ALGORITHM DESIGN AND ANALYSIS 24

BFS - Example
w V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X 3 W
Z 3 W

ALGORITHM DESIGN AND ANALYSIS 25

BFS - Example
y V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X 3 W
Z 3 W

ALGORITHM DESIGN AND ANALYSIS 26

BFS - Example
x V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X 3 W
Z 3 W

ALGORITHM DESIGN AND ANALYSIS 27

BFS - Example
z V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R
T 2 R
Y 2 U
X 3 W
Z 3 W

ALGORITHM DESIGN AND ANALYSIS 28

BFS Analysis
O(V)

Total running time of the BFS

= O(V + E)

O(V + E)

ALGORITHM DESIGN AND ANALYSIS 29

 Breadth-first tree
V d π
▪ Breadth-first search also produces a s
“breadth-first tree” with root s that S 0 NIL
contains all reachable vertices. R 1 S
▪ For any vertex v reachable from s, the r v V 1 S
u
simple path in the breadth-first tree
from s to v corresponds to the shortest U 1 S
path (a path containing the smallest W 2 R
number of edges) from s to v in G. w t y T 2 R
Y 2 U
X 3 W
x z
Z 3 W
Breadth-first trees
▪The PRINT-PATH procedure prints out the vertices on the shortest path from s to v:

ALGORITHM DESIGN AND ANALYSIS 31

Breadth-first trees
To find the shortest path from s to x: V d π
S 0 NIL
R 1 S
V 1 S
U 1 S
W 2 R

➢ Print-path(G,s,x) S R W X T 2 R

➢ Print-path(G,s,w) S R W Y 2 U

➢ Print-path(G,s,r) S R X 3 W

➢ Print-path(G,s,s) Z 3 W
S

ALGORITHM DESIGN AND ANALYSIS 32

Depth-first search
▪ Depth-first search searches “deeper” in the graph whenever possible.
▪ Depth-first search explores edges out of the most recently discovered vertex v that still
has unexplored edges leaving it.
▪ Once all of v ’s edges have been explored, the search “backtrack” to explore edges
leaving the vertex from which v was discovered.

▪ This process continues until all vertices that are reachable from
the original source vertex have been discovered.
▪ If any undiscovered vertices remain, then depth-ûrst search
selects one of them as a new source, repeating the search from
that source.

ALGORITHM DESIGN AND ANALYSIS 33

Depth-first search

Total running time of the DFS

= O(V + E)

ALGORITHM DESIGN AND ANALYSIS 34

Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

a
a
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

c
a
a,c
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

d
c
a
a,c,d
 Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

c
Back edge
a
a,c,d
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

f
c
a
a,c,d,f
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

b
f
c
a
a,c,d,f,b
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

e
b
f
c
a
a,c,d,f,b,e
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

b
f
c
a
a,c,d,f,b,e
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

f
c
a
a,c,d,f,b,e
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

c
a
a,c,d,f,b,e
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

a
a,c,d,f,b,e
Example (DFS)
Show how depth-first search works on the following graph, starting from vertex a.

a,c,d,f,b,e
Questions

ALGORITHM DESIGN AND ANALYSIS 47