MH 3400
ALGORITHMS
FOR THE REAL WORLD
Thomas PEYRIN
Lecture 8: Graphs Basics
MH 3400 - Algorithms for the Real World
Graphs Basics
Outline
▪Graphs Terminology
▪Depth-First Search (DFS)
▪Breadth-First Search (BFS)
▪Directed Graphs
▪Lessons Learned
Algorithms for the Real World Lecture 8 Graphs Basics
Algorithms for the Real World Lecture 8
What is a Graph ?
A graph is a pair (V, E), where
• V is a set of nodes, also called vertices
• E is a collection of pairs of vertices, called edges
• Vertices and edges can store elements
Graphs Basics
Algorithms for the Real World Lecture 8
What is a Graph ?
A graph is a pair (V, E), where
• V is a set of nodes, also called vertices
• E is a collection of pairs of vertices, called edges
• Vertices and edges can store elements
Graphs Basics
John Mary
Jack
Tom
Katie
Algorithms for the Real World Lecture 8
What is a Graph ?
A graph is a pair (V, E), where
• V is a set of nodes, also called vertices
• E is a collection of pairs of vertices, called edges
• Vertices and edges can store elements
Graphs Basics
John Mary
Jack
Tom
Katie
married
married
friend
friend
Work
colleague
friend
friend
Algorithms for the Real World Lecture 8
What is a Simple Graph ?
A simple graph is a pair (V, E), where
• V is a set of nodes, also called vertices
• E is a set of pairs of vertices (with no loop allowed), called edges
• Vertices and edges can store elements
Graphs Basics
John Mary
Jack
Tom
Katie
married
married
friend
friend
Work
colleague
friend
set ≠ collection
Algorithms for the Real World Lecture 8
Directed/Undirected Graph
A graph is directed if all its edges have a origin and a destination
A graph is undirected if all its edges have no origin/destination
Graphs Basics
John Mary
Jack
Tom
Katie
John Mary
Jack
Tom
Katie
Undirected graph: FacebookDirected graph: Twitter or Instagram
Algorithms for the Real World Lecture 8
Graph Abstraction: transportation
Graphs Basics
Singapore MRT/LRT map
Vertex: MRT/LRT station
Edge: MRT/LRT track
Algorithms for the Real World Lecture 8
Graph Abstraction: map
Graphs Basics
Google Maps - NTU
Vertex: intersection
Edge: street
Algorithms for the Real World Lecture 8
Graph Abstraction: neuro-sciences
Graphs Basics
Gnemmi et al. (ReConFig 2015) - DOI:10.1109/ReConFig.2015.7393330
Vertex: gray matter areas
Edge: nerve fibers
Algorithms for the Real World Lecture 8
Graph Abstraction: communications
Graphs Basics
The Internet 2015 - Opte Project (https://web.archive.org/web/20180916235031/http://www.opte.org/the-internet/)
Vertex: websites
Edge: web links
Algorithms for the Real World Lecture 8
Graph Abstraction: electronic circuits
Graphs Basics
Circuit of the Skinny Sbox - https://eprint.iacr.org/2016/660
Vertex: logic gates
Edge: wires
Algorithms for the Real World Lecture 8
Graph Abstraction: social sciences
Graphs Basics
Geographic networks of global refugee flows - GDELT Project (gdeltproject.org)
Vertex: countries
Edge: refugees flows
Algorithms for the Real World Lecture 8 Graphs Basics
Applications of Graphs
Graphs have an enormous range of applications:
• Electronics: printed circuit board, integrated circuit
• Computer Science: networks, Internet, databases, etc.
• Chemistry: study of molecules
• Mathematics: geometry, topology
• Social science: social network analysis
• Transportation: highway network, flight network, water supply, etc.
Graph Vertices Edges
Communications phones, computers cables, connections
Circuits gates, registers, processors wires
Financial stocks transactions
Transportation intersections, points of interest roads
Facebook people friendships
Neural network neurons synapses
Algorithms for the Real World Lecture 8
Graph Terminology
• U and Y are the end vertices or
endpoints of edge a
• Edges a, b, and e are incident on
vertex U
• Vertices U and V are adjacent
(vertices V and Y are not)
• Vertex U has degree 3: deg(U) = 3
• f and g are parallel edges
• h is a self-loop
Graphs Basics
U V
Z
X
Y
a
b
c
d
e
g
f
h
i
Algorithms for the Real World Lecture 8
Graph Terminology
• U and Y are the end vertices or
endpoints of edge a
• Edges a, b, and e are incident on
vertex U
• Vertices U and V are adjacent
(vertices V and Z are not)
• Vertex U has degree 3: deg(U) = 3
• f and g are parallel edges
• h is a self-loop
Graphs Basics
U V
Z
X
Y
a
b
c
d
e
g
f
h
• Walk: sequence of alternating vertices and edges (begins and ends
with a vertex). Ex: (Z,c,Y,a,U,b,Z,d,X) in red
• Path: walk such that all its vertices and edges are distinct.
Ex: (U,b,Z,d,X,f,V) in green
i
Algorithms for the Real World Lecture 8
Graph Terminology
• U and Y are the end vertices or
endpoints of edge a
• Edges a, b, and e are incident on
vertex U
• Vertices U and V are adjacent
(vertices V and Z are not)
• Vertex U has degree 3: deg(U) = 3
• f and g are parallel edges
• h is a self-loop
Graphs Basics
U V
Z
X
Y
a
b
c
d
e
g
f
h
• Circuit: circular sequence of alternating vertices and edges.
Ex: (Y,c,Z,i,V,f,X,d,Z,b,U,a,Y) in red
• Cycle: circuit such that all its vertices and edges are distinct
Ex: (U,e,V,g,X,d,Z,c,Y,a,U) in green
i
Algorithms for the Real World Lecture 8
Graph Terminology
Graphs Basics
subgraph of Ga graph G spanning subgraph of G
(contains all vertices of G)
a connected graph (there is at least a path
between all vertices pairs)
a non connected graph with two
connected components
a forest (graph with no cycle) a tree (a connected
graph with no cycle)
a spanning tree of G (a
spanning subgraph that is a tree)
Algorithms for the Real World Lecture 8
Some Graphs Properties
Graphs Basics
Property 1: if G is a graph with m edges, σ∈ deg = 2
Proof: each edge is counted twice
Property 2: in an undirected simple graph, we have:
m ≤ n (n - 1)/2
Proof: each vertex has degree at most (n - 1)
Question: what is the bound for a directed graph?
Notation: we denote n the number of vertices and m the
number of edges of a graph G.
Algorithms for the Real World Lecture 8
Some Graphs Properties
Graphs Basics
Property 1: if G is a graph with m edges, σ∈ deg = 2
Proof: each edge is counted twice
Property 2: in a simple graph, we have:
m ≤ n (n - 1)/2 if undirected, m ≤ n (n - 1) if directed
Proof: each vertex has (in/out)-degree at most (n - 1).
If directed, we have σ∈ deg =
σ∈ deg =
Notation: we denote n the number of vertices and m the
number of edges of a graph G.
Algorithms for the Real World Lecture 8
Some Graphs Properties
Graphs Basics
Property 1: if G is a graph with m edges, ς∈ () = 2
Proof: each edge is counted twice
Property 2: in a simple graph, we have:
m ≤ n (n - 1)/2 if undirected, m ≤ n (n - 1) if directed
Proof: each vertex has degree at most (n - 1).
If directed, we have σ∈ deg =
σ∈ deg =
Notation: we denote n the number of vertices and m the
number of edges of a graph G.
A simple graph
with n vertices
has at most
O(n2) edges
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Edge list structure: two lists to represent the vertices and edges
A
B C D
w
A
B
C
D
Vertices list Edges list
A
B
x
B
C
y
A
C
z
C
D
w x
y z
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Edge list structure: two lists to represent the vertices and edges
A
B
C
D
Vertices list
w
Edges list
A
B
x
B
C
y
A
C
z
C
D
A
B C D
w x
y z
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Edge list structure: two lists to represent the vertices and edges
Space: O(n + m)
incidentEdges(v): O(m)
areAdjacent (v, w): O(m)
insertVertex(o): O(1)
insertEdge(v, w, o): O(1)
removeVertex(v): O(m)
removeEdge(e): O(1)
A
B
C
D
Vertices list
w
Edges list
A
B
x
B
C
y
A
C
z
C
D
A
B C D
w x
y z
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Adjacency list structure: one lists to represent the vertices and for
each vertex v one list to represent the adjacent vertices of v
Space: O(n + m)
incidentEdges(v): O(deg(v))
areAdjacent (v, w): O(min(deg(v),deg(w)))
insertVertex(o): O(1)
insertEdge(v, w, o): O(1)
removeVertex(v): O(m)
removeEdge(e): O(1)
A
B
C
D
Adjacency list
A
B C D
w x
y z
B C
A C
A B D
C
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Adjacency matrix structure: one (n x n)-matrix to represent all the
possible vertices pairs, and fill the matrix with the corresponding edges
Space: O(n2 + m)
incidentEdges(v): O(n)
areAdjacent (v, w): O(1)
insertVertex(o): O(n2)
insertEdge(v, w, o): O(1)
removeVertex(v): O(n2)
removeEdge(e): O(1)
A
B
C
D
Adjacency matrix
A
B C D
w x
y z
A B C D
w
w
x
x
y
y z
z
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Edge list
structure
Adjacency list Adjacency matrix
Space O(n + m) O(n + m) O(n2 + m)
incidentEdges(v) O(m) O(deg(v)) O(n)
areAdjacent (v, w) O(m) O(min(deg(v),deg(w))) O(1)
insertVertex(o) O(1) O(1) O(n2)
insertEdge(v, w, o) O(1) O(1) O(1)
removeVertex(v) O(m) O(m) O(n2)
removeEdge(e) O(1) O(1) O(1)
Algorithms for the Real World Lecture 8
How Can I Represent/Store a Graph ?
Graphs Basics
Edge list
structure
Adjacency list Adjacency matrix
Space O(n+m) O(n + m) O(n2 + m)
incidentEdges(v) O(m) O(deg(v)) O(n)
areAdjacent (v, w) O(m) O(min(deg(v),deg(w))) O(1)
insertVertex(o) O(1) O(1) O(n2)
insertEdge(v, w, o) O(1) O(1) O(1)
removeVertex(v) O(m) O(m) O(n2)
removeEdge(e) O(1) O(1) O(1)
Graphs tend to be sparse in real life, so n is large and m or deg(v) is not so large.
Adjacency list is usually the classical choice
Algorithms for the Real World Lecture 8
Exploring a Graph
Graphs Basics
Traversing (i.e. exploring) or searching in a graph is a very
crucial action we would like to be able to perform.
Now, there are different ways to explore a graph: should we go:
- “friend-of-friend first” (aka depth-first search)?
Put unvisited vertices on a stack
- “all-my-friends first” (aka breadth-first search) ?
Put unvisited vertices on a queue
MH 3400 - Algorithms for the Real World
Graphs Basics
Outline
▪Graphs Terminology
▪Depth-First Search (DFS)
▪Breadth-First Search (BFS)
▪Directed Graphs
▪Lessons Learned
Algorithms for the Real World Lecture 8 Graphs Basics
Algorithms for the Real World Lecture 8
Lost in a Maze
Graphs Basics
You are stuck in a maze and you would like an algorithm to help you find
the way out.
Algorithms for the Real World Lecture 8
Lost in a Maze
Graphs Basics
You are stuck in a maze and you would like an algorithm to help you find
the way out.
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
start
node
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Pick a neighbour
not yet explored
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Pick a neighbour
not yet explored
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Remove edges that lead to
already explored vertices
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Pick a neighbour
not yet explored
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Remove edges that lead to
already explored vertices
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
backtrack if you
can’t go further
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Pick a neighbour
not yet explored
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
Remove edges that lead to
already explored vertices
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
backtrack if you
can’t go further
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
backtrack if you
can’t go further
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
backtrack if you
can’t go further
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
stop when you’re back to the start node and all
its neighbour have been explored already
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
What is Depth-First Search (DFS) ?
Graphs Basics
edges explored during the discovery of a new
unexplored node are called “discovery edges”
edges explored during the discovery of an
already explored node are called “back edges”
Depth-first search (DFS) is a general technique for traversing a graph,
that uses the backtracking strategy:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
Utilization of DFS
Graphs Basics
A DFS traversal of a graph G will:
• visit all the vertices and edges of G
• find a path from one vertex A to another B: simply start from A
and wait until you reach B (no guarantee that the path will be short)
• determine whether G is connected: if you’re back to the starting
node with all neighbors explored and you still haven’t explored all
nodes of the graph, then the graph is not connected
• compute the connected components of G: once one component
has been fully explored, just pick a new node non explored yet and
repeat. Application: spread of diseases.
• compute a spanning forest of G (or spanning tree if G is
connected): by keeping only discovery edges
• find a cycle in G: if you reach a node already visited during the
DFS, then there is a cycle
Algorithms for the Real World Lecture 8
DFS Algorithm
Graphs Basics
TO BE DONE DURING THE LAB SESSION
Algorithms for the Real World Lecture 8
Complexity Analysis of DFS
Graphs Basics
Note that in DFS every vertex is marked once as explored and
every edge is marked once as explored.
Assume that:
• we have a way to “mark” a vertex or edge as explored, and to test if a
vertex or edge has been explored in O(1) time. This can be done
simply by having a Boolean table of n entries (resp. m entries), each
representing one vertex (resp. one edge).
=> initialization costs O(n+m)
=> checking if the edges/nodes have been explored costs O(n+m)
• the graph is represented by a data structure allowing to find all incident
edges of a vertex v in O(deg(v)) time (ex. the adjacency list structure)
=> rest of the algorithm costs O(∑v deg(v)) = O(2m) = O(m)
computations since incidentEdges is called once for each vertex.
MH 3400 - Algorithms for the Real World
Graphs Basics
Outline
▪Graphs Terminology
▪Depth-First Search (DFS)
▪Breadth-First Search (BFS)
▪Directed Graphs
▪Lessons Learned
Algorithms for the Real World Lecture 8 Graphs Basics
Algorithms for the Real World Lecture 8
Six Degrees of Separation
Graphs Basics
Social Networks such as LinkedIn allow you to see the profile or to
contact people only up to a degree 3 from you in the connection graph.
How can I know if two people are 3 degrees apart or less ?
Algorithms for the Real World Lecture 8
Six Degrees of Separation
Graphs Basics
Social Networks such as LinkedIn allow you to see the profile or to
contact people only up to a degree 3 from you in the connection graph.
How can I know if two people are 3 degrees apart or less ?
Algorithms for the Real World Lecture 8
Six Degrees of Separation
Graphs Basics
Social Networks such as LinkedIn allow you to see the profile or to
contact people only up to a degree 3 from you in the connection graph.
How can I know if two people are 3 degrees apart or less ?
1
1
1
1
1
1
Algorithms for the Real World Lecture 8
Six Degrees of Separation
Graphs Basics
Social Networks such as LinkedIn allow you to see the profile or to
contact people only up to a degree 3 from you in the connection graph.
How can I know if two people are 3 degrees apart or less ?
1 + 2 = 3
1 + 2 = 3
1 + 2 = 3
Algorithms for the Real World Lecture 8
Local Points of Interest
Graphs Basics
You ask your GPS to list you all the restaurants nearby.
How can he find them efficiently ?
Algorithms for the Real World Lecture 8
Local Points of Interest
Graphs Basics
You ask your GPS to list you all the restaurants nearby.
How can he find them efficiently ?
Algorithms for the Real World Lecture 8
Local Points of Interest
Graphs Basics
You ask your GPS to list you all the restaurants nearby.
How can he find them efficiently ?
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
0
start
node
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0
1
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0
1
1st degree neighbours
all explored: we can
go to level 2
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0 2
1
2st degree neighbour
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0 2
1
2
2st degree neighbour
Algorithms for the Real World Lecture 8
What is Breadth-First Search (BFS) ?
Graphs Basics
Breadth-first search (BFS) is a general technique for traversing a
graph, that works level by level:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
0 2
1
2
edges explored during the discovery of a new
unexplored node are called “discovery edges”
edges explored during the discovery of an
already explored node are called “cross edges”
Algorithms for the Real World Lecture 8
Utilization of BFS
Graphs Basics
A BFS traversal of a graph G will:
• visit all the vertices and edges of G
• find the shortest path from one vertex A to another B: simply
start from A and wait until you reach B
• determine whether G is connected: if you can’t go one level
further and you still haven’t explored all nodes of the graph, then the
graph is not connected
• compute the connected components of G: once one component
has been fully explored, just pick a new node non explored yet and
repeat. Application: spread of diseases
• compute a spanning forest of G (or spanning tree if G is
connected): by keeping only discovery edges
• find a cycle in G: if a cross edge exists during the BFS, then there
is a cycle
Algorithms for the Real World Lecture 8
BFS Algorithm
Graphs Basics
TO BE DONE DURING THE LAB SESSION
Algorithms for the Real World Lecture 8
Complexity Analysis of BFS
Graphs Basics
Note that in DFS every vertex is marked once as explored and
every edge is marked once as explored.
Assume that:
• we have a way to “mark” a vertex or edge as explored, and to test if a
vertex or edge has been explored in O(1) time. This can be done
simply by having a Boolean table of n entries (resp. m entries), each
representing one vertex (resp. one edge).
=> initialization costs O(n+m)
=> checking if the edges/nodes have been explored costs O(n+m)
• the graph is represented by a data structure allowing to find all incident
edges of a vertex v in O(deg(v)) time (ex. the adjacency list structure)
=> rest of the algorithm costs O(∑v deg(v)) = O(2m) = O(m)
computations since incidentEdges is called once for each vertex.
MH 3400 - Algorithms for the Real World
Graphs Basics
Outline
▪Graphs Terminology
▪Depth-First Search (DFS)
▪Breadth-First Search (BFS)
▪Directed Graphs
▪Lessons Learned
Algorithms for the Real World Lecture 8 Graphs Basics
Algorithms for the Real World Lecture 8
Task Scheduling
Graphs Basics
Imagine you are project leader for a big construction project. Many tasks
have to be completed, with some particular precedence constraints
(build foundations before the roof !). How to find a good scheduling ?
Algorithms for the Real World Lecture 8
Task Scheduling
Graphs Basics
Atlas of Cyberspace (http://www.cybergeography.org/atlas/topology.html). Social relationships between players in the MUD LambaMOO
Algorithms for the Real World Lecture 8
What is a Digraph ?
A directed graph (or digraph) is a graph whose edges are all
directed. An edge (a,b) only goes from vertex a to vertex b.
Graphs Basics
A B
D
C
E
Property: if a digraph is simple, then m ≤ n(n-1)
Tip: if stored as adjacency list, you can
separate incoming edges and
outcoming edge, so you can list them in
time proportional to their respective size
A
B
C
D
E
Adjacency
list
B
D E
A C
B
D
A
E
C
A D
Algorithms for the Real World Lecture 8
Digraph Applications
Graphs Basics
Many applications: scheduling, electronic circuits, data compression, …
Ex of scheduling: courses requirements
MH3400
MH1301MH1201 MH1402 MH2500
MH1200 MH1401 MH1101
MH1100
Algorithms for the Real World Lecture 8
Applications of Digraphs
Graphs Basics
Many applications: scheduling, electronic circuits, data compression, …
Graph Vertices Edges
Scheduling tasks precedence constraints
Combinatorial circuits logical gates wires
Financial banks transactions
Transportation intersections, points of interest one-way roads
Internet web pages hyperlinks
Twitter people follows
Game game board states allowable moves
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
start
node
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Remove edges coming from already
explored vertices
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Remove edges leading to an already
explored vertices
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
backtrack if you
can’t go further
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
backtrack if you
can’t go further
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
backtrack if you
can’t go further
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Pick a neighbour
not yet explored
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
Remove edges leading to an already
explored vertices
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
backtrack if you
can’t go further
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
stop when you’re back to the start node and all
its neighbour have been explored already
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
stop when you’re back to the start node and all
its neighbour have been explored already
edges explored during the discovery of a new
unexplored node are called “discovery edges”
edges explored during the discovery of an already
explored node are called “non-tree edges”
Algorithms for the Real World Lecture 8
DFS for Digraph
Graphs Basics
Depth-first search (DFS) for a digraph works exactly the same as for a
non-directed graph:
go as far as you can, backtrack when you can’t go further
s
edges explored during the discovery of a new
unexplored node are called “discovery edges”
edges explored during the discovery of an already
explored node are called “non-tree edges”
forward edge: connects a vertex
to a descendant in the DFS tree
backward edge: connects a vertex
to a ancestor in the DFS tree
cross edge: connects a vertex to a
vertex that is neither ancestor nor
descendant in the DFS tree
Node left unexplored
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
0
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
1
1
0
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
1
1
1
0
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
2
0
1
1
1
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
2
0
1
1
1
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
0
1
1
12
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
0
1
1
12
edges explored during the discovery of a new
unexplored node are called “discovery edges”
edges explored during the discovery of an
already explored node are called “cross edges”
Node left unexplored
Algorithms for the Real World Lecture 8
BFS for Digraph
Graphs Basics
Breadth-first search (BFS) for a digraph works exactly the same as for
a non-directed graph:
explore all your direct neighbors first, then all direct neighbors of
your neighbors, etc.
A BFS from a vertex s computes the shortest paths from s
Algorithms for the Real World Lecture 8
Digraph Reachability
Given two vertices a and b, we say that b is reachable from a if there is
a path in the graph from a to b (respecting all the edges directions)
Graphs Basics
Application: garbage collection
• Vertices are object and edges are references to the objects.
• Roots are objects known to be directly accessible by program
(e.g., stack)
• Reachable objects are then those reachable from the roots
following a chain of pointers.
• Mark-sweep algorithm: mark all reachable objects from the
roots, then sweep (if an object is unmarked , it is garbage
and can be added to “free memory” list.
A directed DFS from a vertex s determines the vertices reachable from s. We
can compute the transitive closure of G (full reachability map of G) in O(n(n+m))
r1
r2
r3
r2
Algorithms for the Real World Lecture 8
Strongly Connected Digraphs
Graphs Basics
A digraph G is strongly connected if for any vertices pair (a,b) we have
that b is reachable from a.
Not strongly connected Strongly connected
Algorithm to check strong connectivity: using DFS in O(n+m)
• Pick a vertex v and perform a DFS from v. If there’s a w not visited, output “no”
• Let G’ be G with edges reversed. Perform a DFS from v in G’. If there’s a w not
visited, output “no”, otherwise output “yes”
Algorithms for the Real World Lecture 8
Strongly Connected Components
Graphs Basics
The strongly connected components of a graph are the maximal
subgraphs such that each vertex can reach all other vertices in the
subgraph.
2
3
1
0
5 4
6 8
9 10
11 12
Algorithms for the Real World Lecture 8
Strongly Connected Components
Graphs Basics
The strongly connected components of a graph are the maximal
subgraphs such that each vertex can reach all other vertices in the
subgraph.
2
3
1
0
5 4
6 8
9 10
11 12
Algorithms for the Real World Lecture 8
Strongly Connected Components
Graphs Basics
The strongly connected components of a graph are the maximal
subgraphs such that each vertex can reach all other vertices in the
subgraph.
Strongly connected components for a graph can be found in O(n+m)
time using two DFS, but more complex (Kosaraju’s algorithm)
Application: community detection in social networks (the members of a
community of people are generally strongly connected)
2
3
1
0
5 4
6 8
9 10
11 12
Algorithms for the Real World Lecture 8
Crawling the Web: BFS or DFS ?
Graphs Basics
Web crawlers, which are the data collecting part of search engines, must
explore a graph of hypertext documents by examining its vertices (aka
the documents) and its edges (aka the hyperlinks between documents)
Algorithms for the Real World Lecture 8
Crawling the Web: BFS or DFS ?
Graphs Basics
Web crawlers, which are the data collecting part of search engines, must
explore a graph of hypertext documents by examining its vertices (aka
the documents) and its edges (aka the hyperlinks between documents)
Generally use BFS (optimal), but
can be very memory intensive
Algorithms for the Real World Lecture 8
Directed Acyclic Graph (DAG)
Graphs Basics
A Directed Acyclic Graph (or DAG) is a digraph with no directed cycle.
Directed Acyclic Graph Digraph with a cycle
Very useful to study various problems with precedence constraints, like
scheduling, or inheritance
Algorithms for the Real World Lecture 8
Topological Sort of a DAG
Graphs Basics
A topological ordering of a digraph is a numbering v1, …, vn of the
vertices such that for every edge (vi , vj ), we have i < j.
Th.: A digraph admits a topological ordering if and only if it is a DAG.
In a task scheduling digraph, a topological ordering is a task sequence
that satisfies the precedence constraints
MH3400
MH1301MH1201 MH1402 MH2500
MH1200 MH1401 MH1101
MH1100
v2
v1
v3 v4
v5 v6 v7 v8
v9
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
n = 6
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
6
n = 6
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
6
n = 5
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
n = 5
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
n = 4
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
4
n = 4
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
4
n = 3
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
4
3
n = 3
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
5
6
4
3
n = 2
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
2
5
6
4
3
n = 2
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
2
5
6
4
3
n = 1
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
2
5 1
6
4
3
n = 1
Algorithms for the Real World Lecture 8
Algorithm for Topological Sort
Graphs Basics
Running time: O(n2+m)
• Initial setting require O(n+m)
• Operation for searching for v in the loop is n + n + ... + n = O(n2)
TopologicalSort(G)
H  G # Temporary copy of G
n  G.numVertices()
while H is not empty do:
Let v be a vertex with no
ff re outgoing edges
Label v  n
n  n - 1
Remove v from H
2
5 1
6
4
3
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
a
b d
c
e
f
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b,e}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b,e,a}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b,e,a,d}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b,e,a,d,f}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
a
b d
c
e
f
{c,b,e,a,d,f}
Topological order is {f,d,a,e,b,c}
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
Algorithms for the Real World Lecture 8
Alternative Algorithm for Topological Sort
Graphs Basics
Running time: O(n+m) Same complexity as a normal DFS
3
5 2
6
4
1
TopologicalSort_DFS(G)
compute DFS_postorder(G)
return the nodes in reverse
ff re order
MH 3400 - Algorithms for the Real World
Graphs Basics
Outline
▪Graphs Terminology
▪Depth-First Search (DFS)
▪Breadth-First Search (BFS)
▪Directed Graphs
▪Lessons Learned
Algorithms for the Real World Lecture 8 Graphs Basics
Lessons learned
You must be able to:
• Use the basic terminology of graphs
• Recognize the various types of graphs
• Traverse a graph using DFS or BFS
• Apply DFS/BFS to compute the connected
components of a graph G, or determine whether
G is connected, find a cycle in G, find a path
from one vertex A to another B, etc.
• Apply the topological sort to a DAG
Algorithms for the Real World Lecture 8 Graphs Basics