Description
You can must Java for this programming assignment. You can use your choice of IDE.
What to submit:
Submit your completed code.
Note that it is your responsibility to make sure that your code runs successfully and you provide clear instructions for doing so. You will not get points if we cannot run your code. Also, for full credit, your code should be well-documented with comments.
Problem: Graphs
Implementing Directed Graphs
In this assignment you are asked to write Java classes that implement directed graphs, where the vertices of the graphs are numbers. The implementation should follow the “adjacency list approach” from the lecture. There should be methods for
1. adding individual edges (including the nodes of the edges);
2. constructing a graph from a sequence of edges, specified in a string;
3. printing the nodes with their outgoing edges onto a string.
We suggest the following classes:
A class Vertex Download Vertexhaving the following fields:
– int id: the id of the node;
– char color: that can be ‘w’, ‘g’ or ‘b’;
– Vertex pred: the predecessor vertex (in a tree);
– int dist: the distance from some starting vertex;
– VertexList adj: the vertices reachable from the current vertex traversing an edge;
A class VertexList Download VertexListthat collects Vertex objects. A VertexList consists of instances of the class VertexNode, which are nodes containing a pointer to a Vertex and a pointer next to a VertexNode. The class VertexList should support at least the method – Vertex findOrMake(int i): search in the VertexList for a Vertex whose id is i and return it; if such a vertex is not in the list, create a new Vertex having id = i and an empty adjacency list, add it to the list, and return it.
A class Graph Download Graphhaving the field:
– VertexList vertices: representing the set of vertices of the graph; and at least the following methods:
– static Graph readFromString(String input): construct a new graph from a string storing each all edges divided by semicolons; for example, the graph on the left is encoded by the string on the right:
– void addEdge (int i, int j): add an edge from the node having id i to the node having id j; if the nodes do not exist they are created;
– String writeToString(): output the current graph as a string, formatted as shown in the following figure:
Hint: You want to construct a graph from a string that contains pairs of numbers separated by a semicolon. Each pair specifies an edge from the node with the first number to the node with the second number. You have to split the string to find each edge, and the two nodes in the edge. You find class Split.java Download Split.javawith sample code for splitting strings. You will need to extend this code to use it in the methods.
2. Graph Traversal
Add to your Graph class the following methods for graph traversal:
Graph BFS(Vertex s): implementing breadth-first search (BFS) over the graph with start node s, and returning a new Graph, representing the tree of the BFS traversal;
Graph recDFS(): implementing depth-first search (DFS) over the graph as a recursive algorithm; the method returns a new Graph, representing the depth-first forest of the traversal;
Graph itDFS(): implementing depth-first search (DFS) over the graph by an algorithm that maintains an explicit stack; as the previous algorithm, it returns the forest of the traversal;
IntList topSort(): returns a list with a topological sort of the vertex ids of the graph, if the graph is acyclic, and returns null otherwise.
Unformatted Attachment Preview
Graph Introduction
CS 146: Data Structure and Algorithms
Fall 2023
Lecturer: Tahereh Arabghalizi, PhD (She, Her)
Department of Computer Science
Outline
Graphs: definitions
Representations
Breadth-first search
Depth-first search
Example
LU
ZH
BS
ZG
VD
OW
VS
GE
NW
SO
UR
AG
GL
NE
FR
TI
JU
BE
SZ
BL
GR
SH
SG
TG
AL
AR
Same Example (Better Layout)
JU
BS
BL
AG
SO
SH
ZH
ZG
NE
TG
LU
AR
SG
SZ
NW
AL
GL
OW
VD
GE
FR
BE
UR
VS
TI
GR
Many Models and Applications
Social networks: who knows who
The Web graph: which page links to which
The Internet graph: which router links to which
Citation graphs: who references whose papers
Planar graphs: which country is next to which
Well-shaped meshes: pretty pictures with triangles
Geometric graphs: who is near who
Random graphs: whichever. . .
Examples and descriptions taken from Daniel A. Spielman’s course “Graphs and Networks.”
Definitions
A graph
G = (V , E)
V is the set of vertices (also called nodes)
E is the set of edges
Definitions
A graph
G = (V , E)
V is the set of vertices (also called nodes)
E is the set of edges
!
E ⊆ V × V, i.e., E is a relation between vertices
!
an edge e = (u, v) ∈ V is a pair of vertices u ∈ V and v ∈ V
Definitions
A graph
G = (V , E)
V is the set of vertices (also called nodes)
E is the set of edges
!
E ⊆ V × V, i.e., E is a relation between vertices
!
an edge e = (u, v) ∈ V is a pair of vertices u ∈ V and v ∈ V
An undirected graph is characterized by a symmetric relation between vertices
!
an edge is a set e = {u, v } of two vertices
Example (1)
JU
BS
BL
AG
SO
SH
ZH
ZG
NE
TG
LU
AR
SG
SZ
NW
AL
GL
OW
VD
GE
FR
BE
UR
VS
TI
GR
Example (3)
xserver-xorg-core
xserver-common
x11-xkb-utils
x11-common
libxaw7
lsb-base
libxmu6
libxkbfile1
libxt6
libx11-6
libx11-data
xkb-data
libxshmfence1
libxpm4
libsm6
libc6
libgcc1
gcc-6-base
libxext6
▪ Graph type
▪ Undirected: edge , = ,
▪ Directed: edge , goes from vertex to vertex ; , ≠ ,
▪ Weighted: edges associate with weights
3
1
2
4
5
3
1
2
4
5
How many edges at most can a undirected (or directed) graph have?
6
▪ Adjacent (相鄰)
▪ If there is an edge
, , then and are adjacent.
▪ Incident (作用)
▪ If there is an edge
, , the edge , is incident from and
is incident to .
▪ Subgraph (子圖)
▪ If a graph ′ = ′ , ′ is a subgraph of = , , then ′ ⊆
and ′ ⊆
7
▪ Degree
▪ The degree of a vertex is the number of edges incident on
▪ In-degree of : #edges , in a directed graph
▪ Out-degree of : #edges , in a directed graph
▪ Degree = in-degree + out-degree
▪ Isolated vertex: degree = 0
σ
=
2
8
▪ Path
▪ a sequence of edges that connect a sequence of vertices
▪ If there is a path from (source) to (target), there are a sequence
of edges , 1 , 1 , 2 , … , −1 , , ( , )
▪ Reachable: is reachable from if there exists a path from to
▪ Simple Path
▪ All vertices except for and are all distinct
A path that does not repeat vertices
▪ Cycle
▪ A simple path where and are the same
▪ Subpath
▪ A subsequence of the path
9
▪ Connected
▪ Two vertices are connected if there is a path between them
▪ A connected graph has a path from every vertex to every other
▪ Tree
▪ a connected, acyclic, undirected graph
▪ Forest
▪ an acyclic, undirected but possibly disconnected graph
3
1
2
4
5
3
1
2
4
5
3
1
2
4
5
10
Graph Representation
How do we represent a graph G = (E, V ) in a computer?
Graph Representation
How do we represent a graph G = (E, V ) in a computer?
Adjacency-list representation
V = {1, 2, . . . !V !}
G consists of an array Adj
A vertex u ∈ V is represented by an element in the array Adj
Graph Representation
How do we represent a graph G = (E, V ) in a computer?
Adjacency-list representation
V = {1, 2, . . . !V !}
G consists of an array Adj
A vertex u ∈ V is represented by an element in the array Adj
Adj[u] is the adjacency list of vertex u
!
the list of the vertices that are adjacent to u
!
i.e., the list of all v such that (u, v) ∈ E
Example
9
10
11
12
5
6
7
8
1
2
3
4
Example
Adj
9
10
11
12
5
6
7
8
1
2
3
4
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
O(1)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
O(1)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
O(1)
optimal
Θ(!V !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
O(1)
optimal
Iteration through E?
Θ(!V !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
okay (not optimal)
Θ(!V ! + !E !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
okay (not optimal)
Checking (u, v) ∈ E?
Θ(!V ! + !E !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
Θ(!V ! + !E !)
okay (not optimal)
Checking (u, v) ∈ E?
O(!V !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Using the Adjacency List
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V ! + !E !)
okay (not optimal)
Checking (u, v) ∈ E?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
bad
O(!V !)
Adj
1
2
3
4
5
6
7
8
9
10
11
12
5
3
4
7
9
2
8
11
10
12
6
7
7
7
10
12
9
11
Graph Representation (2)
Graph Representation (2)
Adjacency-matrix representation
V = {1, 2, . . . !V !}
G consists of a !V ! × !V ! matrix A
A = (aij ) such that
aij =
!
1
0
if (i, j) ∈ E
otherwise
Example
9
10
11
12
5
6
7
8
1
2
3
4
Example
1 2 3 4 5 6 7 8 9 10 11 12
9
10
11
5
6
7
1
2
3
1
2
3
12
4
5
6
8
7
8
9
4
10
11
12
Example
9
10
11
5
6
7
1
2
3
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
2
1
1
3
12
1
4
1
5
1
1
1
6
8
1
1 1
7
1 1
8
1
9
4
10
1
11
12
Using the Adjacency Matrix
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
O(1)
optimal
Θ(!V !)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
O(1)
optimal
Iteration through E?
Θ(!V !)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
possibly very bad
Θ(!V !2)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
possibly very bad
Checking (u, v) ∈ E?
Θ(!V !2)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
Θ(!V !2)
possibly very bad
Checking (u, v) ∈ E?
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Using the Adjacency Matrix
Accessing a vertex u?
!
optimal
Iteration through V ?
!
Θ(!V !2)
possibly very bad
Checking (u, v) ∈ E?
!
Θ(!V !)
optimal
Iteration through E?
!
O(1)
optimal
O(1)
1
2
3
4
5
6
7
8
9
10
11
12
1 2 3 4 5 6 7 8 9 10 11 12
1 1
1
1
1
1
1
1
1
1
1
1
1 1
1 1
1
1
Space Complexity
Space Complexity
Adjacency-list representation
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
optimal
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
optimal
Adjacency-matrix representation
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
optimal
Adjacency-matrix representation
Θ(!V !2)
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
optimal
Adjacency-matrix representation
Θ(!V !2)
possibly very bad
Space Complexity
Adjacency-list representation
Θ(!V ! + !E !)
optimal
Adjacency-matrix representation
Θ(!V !2)
possibly very bad
When is the adjacency-matrix “very bad”?
Choosing a Graph Representation
Adjacency-list representation
!
generally good, especially for its optimal space complexity
!
bad for dense graphs and algorithms that require random access to edges
!
preferable for sparse graphs or graphs with low degree
Choosing a Graph Representation
Adjacency-list representation
!
generally good, especially for its optimal space complexity
!
bad for dense graphs and algorithms that require random access to edges
!
preferable for sparse graphs or graphs with low degree
Adjacency-matrix representation
!
suffers from a bad space complexity
!
good for algorithms that require random access to edges
!
preferable for dense graphs
▪ From a source vertex, systematically follow the edges of a
graph to visit all reachable vertices of the graph
▪ Useful to discover the structure of a graph
▪ Standard graph-searching algorithms
▪ Breadth-First Search (BFS, 廣度優先搜尋)
▪ Depth-First Search (DFS, 深度優先搜尋)
26
Breadth-first traversal
Consider implementing a breadth-first traversal on a graph:
– Choose any vertex, mark it as visited and push it onto queue
– While the queue is not empty:
• Pop to top vertex v from the queue
• For each vertex adjacent to v that has not been visited:
– Mark it visited, and
– Push it onto the queue
This continues until the queue is empty
– Note: if there are no unvisited vertices, the graph is connected,
BFS can be used for disconnected graphs. To ensure that BFS visits all vertices in a
disconnected graph, you can modify the BFS algorithm to handle disconnected components.
Example
Consider this graph
Example
Performing a breadth-first traversal
– Push the first vertex onto the queue
A
Example
Performing a breadth-first traversal
– Pop A and push B, C and E
A
B
C
E
Example
Performing a breadth-first traversal:
– Pop B and push D
A, B
C
E
D
Example
Performing a breadth-first traversal:
– Pop C and push F
A, B, C
E
D
F
Example
Performing a breadth-first traversal:
– Pop E and push G and H
A, B, C, E
D
F
G
H
Example
Performing a breadth-first traversal:
– Pop D
A, B, C, E, D
F
G
H
Example
Performing a breadth-first traversal:
– Pop F
A, B, C, E, D, F
G
H
Example
Performing a breadth-first traversal:
– Pop G and push I
A, B, C, E, D, F, G
H
I
Example
Performing a breadth-first traversal:
– Pop H
A, B, C, E, D, F, G, H
I
Example
Performing a breadth-first traversal:
– Pop I
A, B, C, E, D, F, G, H, I
Example
Performing a breadth-first traversal:
– The queue is empty: we are finished
A, B, C, E, D, F, G, H, I
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
d store the distance (or level) of each vertex from the source vertex
s in terms of the number of edges.
π stores the predecessor (or parent) of each vertex.
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=1
Q=∅
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=1
Q = {5}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=1
Q = {5, 6}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=5
Q = {6}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=5
Q = {6, 9}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=6
Q = {9}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=6
Q = {9, 2, 7}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=6
Q = {9, 2, 7}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=9
Q = {2, 7}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=9
Q = {2, 7, 10}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=2
Q = {7, 10}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=2
Q = {7, 10, 3}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=7
Q = {10, 3}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=7
Q = {10, 3, 8}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=7
Q = {10, 3, 8, 11}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u = 10
Q = {3, 8, 11}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=3
Q = {8, 11}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=3
Q = {8, 11, 4}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=8
Q = {11, 4}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=8
Q = {11, 4, 12}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u = 11
Q = {4, 12}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u=4
Q = {12}
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
u = 12
Q=∅
BFS Algorithm
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
9
10
11
12
5
6
7
8
1
2
3
4
Complexity of BFS
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
Complexity of BFS
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
We enqueue a vertex only if
it is white, and we
immediately color it gray;
thus, we enqueue every
vertex at most once
Complexity of BFS
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
We enqueue a vertex only if
it is white, and we
immediately color it gray;
thus, we enqueue every
vertex at most once
So, the (dequeue) while loop
executes O(!V !) times
Complexity of BFS
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
We enqueue a vertex only if
it is white, and we
immediately color it gray;
thus, we enqueue every
vertex at most once
So, the (dequeue) while loop
executes O(!V !) times
For each vertex u, the inner
loop executes Θ(!Eu !), for a
total of O(!E !) steps
Complexity of BFS
BFS(G, s)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for each vertex u ∈ V(G) {s}
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color [s] = GRAY
d [ s] = 0
π[s] = NIL
Q = ∅
ENQUEUE(Q, s)
while Q ! ∅
u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v ] = = WHITE
color[v ] = GRAY
d[v ] = d[u] + 1
π[v ] = u
ENQUEUE(Q, v)
color[u] = BLACK
We enqueue a vertex only if
it is white, and we
immediately color it gray;
thus, we enqueue every
vertex at most once
So, the (dequeue) while loop
executes O(!V !) times
For each vertex u, the inner
loop executes Θ(!Eu !), for a
total of O(!E !) steps
So, O(!V ! + !E !)
Depth-first traversal
Consider implementing a depth-first traversal on a graph:
– Choose any vertex, mark it as visited
– From that vertex:
• If there is another adjacent vertex not yet visited, go to it
• Otherwise, go back to the most previous vertex that has not yet had all of its
adjacent vertices visited and continue from there
– Continue until no visited vertices have unvisited adjacent vertices
Two implementations:
– Recursive
– Iterative
DFS Algorithm
DFS(G)
1
2
3
4
5
6
7
for each vertex u ∈ V(G)
color[u] = WHITE
π[u] = NIL
time = 0 // “global” variable
for each vertex u ∈ V(G)
if color[u] == WHITE
DFS-VISIT (u)
DFS-VISIT (u)
1
2
3
4
5
6
7
8
9
10
color[u] = GREY
time = time + 1
d[u] = time
for each v ∈ Adj[u]
if color[v ] == WHITE
π[v ] = u
DFS-VISIT(v)
color[u] = BLACK
time = time + 1
f [u] = time
Example
Perform a recursive depth-first traversal on this same graph
Example
Performing a recursive depth-first traversal:
– Visit the first node
A
Example
Performing a recursive depth-first traversal:
– A has an unvisited neighbor
A, B
Example
Performing a recursive depth-first traversal:
– B has an unvisited neighbor
A, B, C
Example
Performing a recursive depth-first traversal:
– C has an unvisited neighbor
A, B, C, D
Example
Performing a recursive depth-first traversal:
– D has no unvisited neighbors, so we return to C
A, B, C, D, E
Example
Performing a recursive depth-first traversal:
– E has an unvisited neighbor
A, B, C, D, E, G
Example
Performing a recursive depth-first traversal:
– F has an unvisited neighbor
A, B, C, D, E, G, I
Example
Performing a recursive depth-first traversal:
– H has an unvisited neighbor
A, B, C, D, E, G, I, H
Example
Performing a recursive depth-first traversal:
– We recurse back to C which has an unvisited neighbour
A, B, C, D, E, G, I, H, F
Example
Performing a recursive depth-first traversal:
– We recurse finding that no other nodes have unvisited neighbours
A, B, C, D, E, G, I, H, F
Comparison
The order in which vertices can differ greatly
– An iterative depth-first traversal may also be different again
A, B, C, E, D, F, G, H, I
A, B, C, D, E, G, I, H, F
Complexity of DFS
Complexity of DFS
The loop in DFS-VISIT (u) (lines 4–7) accounts for Θ(!Eu !)
Complexity of DFS
The loop in DFS-VISIT (u) (lines 4–7) accounts for Θ(!Eu !)
We call DFS-VISIT (u) once for each vertex u
!
either in DFS, or recursively in DFS-VISIT
!
because we call it only if color[u] = WHITE , but then we immediately set
color[u] = GREY
Complexity of DFS
The loop in DFS-VISIT (u) (lines 4–7) accounts for Θ(!Eu !)
We call DFS-VISIT (u) once for each vertex u
!
either in DFS, or recursively in DFS-VISIT
!
because we call it only if color[u] = WHITE , but then we immediately set
color[u] = GREY
So, the overall complexity is Θ(!V ! + !E !)
Applications
Applications of tree traversals include:
– Determining connectiveness and finding connected sub-graphs
– Determining the path length from one vertex to all others
– Testing if a graph is bipartite
– Determining maximum flow
– Cheney’s algorithm for garbage collection
Questions?
• Upcoming: HW 11, Programming Assignment #2
• Next Session: Topological Sort
Topological Sort
CS 146: Data Structure and Algorithms
Fall 2023
Lecturer: Tahereh Arabghalizi, PhD (She, Her)
Department of Computer Science
Motivation
• Many real-world situations can be modeled as a graph with directed
edges where some events must occur before others.
• School class prerequisites
• Program dependencies
• Event Scheduling
• Assembly instructions
• Etc.
• There is an ordering on the nodes of the graph.
• The orderings are NOT unique.
Dependency Graphs: Tasks
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare Egg
Mixture
Add Eggs &
Cook
Plate
Omelette
and Toast
How can I parallelize
these tasks to finish
more quickly?
7
Dependency Graphs: Tasks
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare Egg
Mixture
Add Eggs &
Cook
Plate
Omelette
and Toast
What step is best to
optimize in this
production process?
8
Dependency Graphs: Orderings
CS 106A
CS
106B/X
CS 103
CS 107
CS 109
CS 221
CS 110
CS 161
What are valid orderings
of these tasks?
9
Dependency Graphs: Compilers
LoginUI
MainUI
Bundle
AppDB
Toolbar
DataTypes
In what order should we
recompile source files
with dependencies?
11
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Which tasks
could we
complete first?
13
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Which tasks
could we
complete first?
14
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
15
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
16
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
17
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
18
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
19
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
20
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
21
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
22
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
23
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
24
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
25
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
26
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
Plate
Food
27
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
Plate
Food
28
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
Plate
Food
29
Topological Sort
Given a directed (acyclic!) graph G = (V, E), a topological sort is a total
ordering of G’s vertices such that for every edge (v, w) in E, vertex v
precedes w in the ordering.
CS 106A
CS
106B/X
CS 103
CS 107
CS 109
CS 221
CS 110
CS 161
30
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Prepare
Eggs
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Sauté
Veggies
Add
Eggs &
Cook
Plate
Food
31
Topological Sort
Toast Bread
Chop
Veggies
Butter Toast
Sauté
Veggies
Add Eggs &
Cook
Plate Food
Toast
Bread
Chop
Veggies
Butter
Toast
Prepare
Eggs
Prepare
Eggs
Given a directed graph G = (V,
E), a topological sort is a total
ordering of G’s vertices such
that for every edge (v, w) in E,
vertex v precedes w in the
ordering.
Sauté
Veggies
Add
Eggs &
Cook
Plate
Food
32
Topological Sort: Idea
1. Find node with in-degree of 0 WHY?
2. Add it at the end of our topological ordering so far, and remove it
and its edges from the graph
3. Repeat until no nodes left
35
Topological Sort Algorithm
ordering := { }.
// (empty list)
Repeat until graph is empty:
Find a vertex v with in-degree of 0
Delete v and its outgoing edges from graph
ordering += v
• This algorithm modifies the passed-in graph L
• Have we handled all edge cases?
• What is the runtime of this algorithm?
36
Topological Sort Algorithm
ordering := { }.
// (empty list)
Repeat until graph is empty:
Find a vertex v with in-degree of 0
Delete v and its outgoing edges from graph
ordering += v
• This algorithm modifies the passed-in graph L
• Have we handled all edge cases?
• What is the runtime of th
