CSC2105: Algorithms

Graph - Introduction

Mashiour Rahman
mashiour@aiub.edu
American International University Bangladesh
 Graph - Introduction
Reference:
• CLRS Appendix B.4, Chapters 22, 24-26

Objectives:
• To learn several significant graph algorithms and their
applications
a. Graph search (BFS, DFS)
b. Bellman/Ford and Dijkstra’s shortest path algorithms (Greedy)
c. Floyd’s algorithm (Dynamic Programming)
d. Network flows

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  2

 Motivation
State-space search in Artificial Intelligence
Geographical information systems, electronic
street directory
Logistics and supply chain management
Telecommunications network design
Many more industry applications

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  3

 Review: Graphs
Graph G = (V, E)
V = {1,…n} = set of vertices, E = set of e edges
Undirected graph:
edge (u, v) = edge (v, u)
no self-loops
Directed graph (digraph):
edge (u, v) goes from vertex u to vertex v
Sparse graph:
e = O(n), dense otherwise
A weighted graph associates weights with either the edges or the
vertices
Degree of a vertex v:
deg(v) = number of edges adjacent on v (in-degree and out-degree for
directed graphs)
Mashiour AIUB::CSC2105::Algorithms Graph Introduction  4
 Examples of Graphs

Directed & Undirected graphs.

a) A directed graph G= (V, E), where V = {1,2,3,4,5,6} and E={(1,2),
(2,2),(2,4),(2,5),(4,1),(4,5),(5,4),(3,6)}. The edge (2,2) is self loop.
b) An undirected graph G = (V,E), where V = {1,2,3,4,5,6} and E =
{(1,2),(1,5),(2,5),(3,6)}. The vertex 4 is isolated.
c) The subgraph of the graph in part (a) induced by vertex set {1,2,3,6}

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  5

 Review: Graphs
Acyclic : if a graph contains no cycles
DAG : Directed acyclic graphs
Connected : if every vertex of a graph can reach
every other vertex, i.e., every pair of vertices is
connected by a path
Connected Components : equivalence classes of
vertices under “is reachable from” relation
Strongly connected : every 2 vertices are reachable
from each other (in a digraph)

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  6

 Forests, DAG, Components

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  7

 Review: Representing Graphs
Adjacency matrix: represents a graph as n x n matrix A:
A[i, j] = 1 if edge (i, j) E (or weight of edge)
= 0 if edge (i, j) E
Storage requirements: O(n2)
A dense representation
But, can be very efficient for small graphs
Especially if store just one bit/edge
Undirected graph: only need half of matrix

Adjacency list: list of adjacent vertices

For each vertex v V, store a list of vertices adjacent to v
Storage requirements: O(n+e)
Good for large, sparse graphs (e.g., planar maps)

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  8

 Review: Representing Graphs

Two representations of an undirected graph.

a) An undirected graph G having five vertices and seven
edges.
b) An adjacency-list representation of G.
c) The adjacency-matrix representation of G.
Mashiour AIUB::CSC2105::Algorithms Graph Introduction  9
 Graph Searching
Given: a graph G = (V, E), directed or undirected
Goal: methodically explore every vertex and 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
Depth-first search
Other variants: best-first, iterated deepening search,
etc.

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  10

 Depth-First Search (DFS)
Explore “deeper” in the graph whenever possible
Edges are explored out of the most recently discovered vertex v that
still has unexplored edges (LIFO)

When all of v’s edges have been explored, backtrack to the vertex from
which v was discovered

computes 2 timestamps: d[ ] (discovered) and f[ ] (finished)

builds one or more depth-first tree(s) (depth-first forest)

Algorithm colors each vertex

WHITE: undiscovered

GRAY: discovered, in process

BLACK: finished, all adjacent vertices have been discovered

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  11

 Depth-First Search: The Code
DFS(G) DFS_Visit(u)
{
{ color[u] = GREY;
for each vertex u V time = time+1;
color[u] = WHITE; d[u] = time; // compute d[]
time = 0;
for each v adjacent to u
if (color[v] == WHITE)
for each vertex u V p[v]= u // build tree
if (color[u] == WHITE) DFS_Visit(v);
DFS_Visit(u); color[u] = BLACK;
} time = time+1;
f[u] = time; // compute f[]
}

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  12

 DFS Analysis
Running time of DFS = O(n+e)
DFS (excluding DFS_Visit) takes O(n) time
DFS_Visit:
DFS_Visit( v ) is called exactly once for each vertex v
During DFS_Visit( v ), adjacency list of v is scanned once
sum of lengths of adjacency lists = O(e)

This type of aggregate analysis is an informal

example of amortized analysis

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  13

 DFS Classification of Edges
DFS can be used to classify edges of G:
1. Tree edges: edges in the depth-first forest.
2. Back edges: edges (u, v) connecting a vertex u to an
ancestor v in a depth-first tree.
3. Forward edges: non-tree edges (u, v) connecting a vertex
u to a descendant v in a depth-first tree.
4. Cross edges: all other edges.

DFS yields valuable information about the structure

of a graph.

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  14

 Operations of DFS

u v w
Undiscovered

Discovered,
On Process

Finished,
Finished all
adjacent vertices x y z
have been
discovered

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  15

 Operations of DFS

u v w
Undiscovered 1/

Discovered,
On Process

Finished,
Finished all
adjacent vertices x y z
have been
discovered

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  16

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process

Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  17

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  18

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process
4/ 3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  19

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process
4/ 3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  20

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process
4/5
4/ 3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  21

 Operations of DFS

u v w
Undiscovered 1/ 2/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  22

 Operations of DFS

u v w
Undiscovered 1/ 2/7
2/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  23

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  24

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  25

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  26

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/

Discovered,
On Process
4/5
4/ 3/6
3/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time
Cross Edge

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  27

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/

Discovered,
On Process
4/5
4/ 3/6
3/ 10/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time
Cross Edge

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  28

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/

Discovered,
On Process
4/5
4/ 3/6
3/ 10/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time
Cross Edge

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  29

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/

Discovered,
On Process
4/5
4/ 3/6
3/ 10/11
10/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time
Cross Edge

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  30

 Operations of DFS

u v w
Undiscovered 1/8
1/ 2/7
2/ 9/12
9/

Discovered,
On Process
4/5
4/ 3/6
3/ 10/11
10/
Finished,
Finished all
adjacent vertices x y z
have been
Tree edge
discovered
Back Edge

Forward Edge
Discover time/ Finish time
Cross Edge

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  31

 Cycle Detection
Theorem: An undirected graph is acyclic iff a DFS
yields no back edges
Proof
If acyclic, no back edges by definition (because a back edge
implies a cycle)
If no back edges, acyclic
No back edges implies only tree edges (Why?)
Only tree edges implies we have a tree or a forest
Which by definition is acyclic

Thus, can run DFS to find whether a graph has a

cycle. How would you modify the code to detect
cycles?

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  32

 Directed Acyclic Graph (DAG)
Arises in many applications where there are
precedence or ordering constraints (e.g. scheduling
problems)
if there are a series of tasks to be performed, and certain
tasks must precede other tasks

In general, a precedence constraint graph is a DAG,

in which vertices are tasks and edge (u, v) means that
task u must be completed before task v begins

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  33

 Topological Sort
Find a linear ordering of all vertices of the DAG such
that if G contains an edge (u, v), u appears before v
in the ordering.
In general, there may be many legal topological
orders for a given DAG.
Idea:
1. Call DFS(G) to compute finishing time f[ ]
2. Insert vertices onto a linked list according to
decreasing order of f[ ]

How to modify DFS to perform Topological Sort in O(n+e)

time?

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  34

 Strongly Connected Components
Digraphs are often used to model communication and
transportation networks

People want to know that the networks are complete in the

sense that from any location it is possible to reach another
location in the digraph

How to find strongly connected components (SCC) of a

digraph?

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  35

 Algorithm (SCC)
Strongly-Connected-Components(G)
1. call DFS(G) to compute finish times f[]
2. compute GT
3. call DFS(GT) and consider vertices in decreasing f[]
computed in step 1
4. output vertices of each tree in DFS(GT) as separate
strongly connected component

Total running time ΘT(n + e)

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  36

 Breadth-First Search (BFS)
Given source vertex s,
systematically explore the breadth of the frontier to
discover every vertex reachable from s
computes the distance d[ ] from s to all reachable vertices
builds a breadth-first tree rooted at s

Algorithm
colors each vertex:
WHITE : undiscovered
GRAY: discovered, in process
BLACK: finished, all adjacent vertices have been discovered

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  37

 BFS (Intuition)

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  38

 BFS: The Code
BFS(G, s) {
initialize vertices;
Q = {s};
while (Q not empty) {
u = Dequeue(Q);
for each v adjacent to u do {
if (color[v] == WHITE) {
color[v] = GRAY;
d[v] = d[u] + 1;// compute d[]
p[v] = u; // build BFS tree
Enqueue(Q, v);
}
}
color[u] = BLACK;
}
}

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  39

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  40

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  41

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  42

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  43

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  44

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  45

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  46

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  47

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  48

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  49

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  50

 BFS Example

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  51

 BFS Analysis
initialize : O(n)
Loop: Queue operations and Adjacency checks
Queue operations
each vertex is enqueued/dequeued at most once. Why?
each operation takes O(1) time, hence O(n)

Adjacency checks
adjacency list of each vertex is scanned at most once
sum of lengths of adjacency lists = O(e)

Total run time of BFS = O(n+e)

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  52

 Breadth-First Search: Properties
What do we get the end of BFS?
1. d[v] = shortest-path distance from s to v, i.e.
minimum number of edges from s to v, or ∞ if v not
reachable from s
Proof : refer CLRS

2. a breadth-first tree, in which path from root s to

any vertex v represent a shortest path
Thus can use BFS to calculate shortest path from one
vertex to another in O(n+e) time, for unweighted graphs.

Mashiour AIUB::CSC2105::Algorithms Graph Introduction  53