Graphs

• Motivation and Terminology

• Representations
• Traversals
• Three Problems

1
 Graphs
A graph G consists of a set of vertices V together with a
set E of vertex pairs or edges.
G = (V,E) [in some texts they use G(V,E)].
We also use V and E to represent # of nodes and edges
Graphs are important because any binary relation is a
graph, so graphs can be used to represent essentially any
relationship.

2
 Graph Interpretations
Living Room Den Bedroom The vertices could represent
rooms in a house, and the
edges could indicate which of
those rooms are connected to
Kitchen Hallway Bath
each other.

Living Den Sometimes a using a graph

Room
Hall
will be an easy simplification
Bed for a problem.
Kitchen Bath

Apartment Blueprint 3
 More interpretations
• Vertices are cities and edges are the roads
connecting them.
• Edges are the components in a circuit and
vertices are junctions where they connect.
• Vertices are software packages and edges
indicate those that can interact.
• Edges are phone conversations and vertices
are the households being connected.
4
 Friendship Graphs
A B C

D E
F

Each vertex represents a person, and each edge indicates

that the two people are friends.
5
 Graph Terminology
Directed and undirected graphs
A graph is said to be undirected if edge (x, y) always implies
(y, x). Otherwise it is said to be directed. Often called an arc.
Loops, multiedges, and simple graphs
An edge of the form (x, x) is said to be a loop. If x was y’s
friend several times over, we can model this relationship using
multiedges. A graph is said to be simple if it contains no loops
or multiedges.
Weighted edges
A graph is said to be weighted if each edge has an associated
numerical attribute. In an unweighted graph, all edges are
assumed to be of equal weight. 6
 Kinds of Graphs

Weighted Undirected
Undirected graph Directed graph graph

Finite graph Trivial graph

7
Infinite graph
 Kinds of Graphs

Simple graph Parallel graph Null graph

Complete graph Bipartite graph Directed Acyclic graph

8
 Terminology continued...
Paths
A path is any sequence of edges that connect two vertices. A
simple path never goes through any vertex more than once. The
shortest path is the minimum number edges needed to connect
two vertices.
Connectivity
The “six degrees of separation” theory argues that there is
always a short path between any two people in the world. A
graph is connected if there a path between any two vertices. A
directed graph is strongly connected if there is always a directed
path between vertices. Any subgraph that is connected can be
referred to as a connected component.
9
 Path and Connectivity

Disconnected graph
Connected graph

Path in a graph 10
Path in a graph
 Still More Terminology...
Degree and graph types
The degree of a vertex is the number of edges connected to it.
The most popular person will have a vertex of the highest degree.
Remote hermits may have degree-zero vertices. In dense
graphs, most vertices have high degree. In sparse graphs, most
vertices have low degree. In a regular graph, all vertices have
exactly the same degree. Degree can be Indegree and/or
Outdegree.
Clique
A graph is called complete if every pair of vertices is connected
by an edge. A clique is a sub-graph that is complete.
A clique in an undirected graph is a subset of vertices such that every two
distinct vertices in the subset are adjacent — that is, there is an edge
connecting every pair of vertices in the clique. 11
 Degree

Graph with varying

degree Regular Graph (with
same degree)

12
Clique

13
 Yet More Terminology...
Cycles and Dags
A cycle is a path where the last vertex is adjacent to the first. A
cycle in which no vertex is repeated is said to be a simple cycle.
The shortest cycle in a graph determines the graph’s girth. A
simple cycle that passes through every vertex is said to be a
Hamiltonian cycle. An undirected graph with no cycles is a
tree if it is connected, or a forest if it is not. A directed graph
with no directed cycles is said to be a directed acyclic graph (or
a DAG)

14
 Cycles and DAGs

Trees in a Forest
Graph with cycles

DAG 15
 Hamiltonian Cycle/Path
• Hamiltonian cycle (HC): is a cycle which passes once
and exactly once through every vertex of G and returns to
starting position
• Hamiltonian path: is a path which passes once and
exactly once through every vertex of G (G can be
digraph).
• A graph is Hamiltonian iff a Hamiltonian cycle(HC)
exists.
• This problem can be solved using backtracking approach
05/19/2025 Amrita School of Engineering 16
 Example

v1
]

05/19/2025 Amrita School of Engineering 17

 18

05/19/2025
 A) Hamiltonian path BCGFAE and
NO Hamiltonian cycle
B) No Hamiltonian path and cycle

C) Hamiltonian path AEFBCGHD

Hamiltonian cycle AEFBCGHDA
Hamiltonian Graph
D) Hamiltonian path ABCDEFG
Hamiltonian cycle ABCDEFGA
Hamiltonian Graph

E) No Hamiltonian path and cycle

F) Hamiltonian path
ABCDEFGHI
Hamiltonian cycle
ABCDEFGHIA
Amrita School of Engineering
Hamiltonian Graph

05/19/2025 19
• Graph G = (V, E) Graphs
– V = set of vertices
– E = set of edges  (VV)
• Types of graphs
– Undirected: edge (u, v) = (v, u); for all v, (v, v)  E (No self
loops.)
– Directed: (u, v) is edge from u to v, denoted as u  v. Self loops
are allowed (also called as digraph)
– Weighted: each edge has an associated weight, given by a weight
function w : E  R.
– Dense: |E|  |V|2.
– Sparse: |E| << |V|2.
• |E| = O(|V|2)
20
Strongly Connected Components
of a Digraph
• Strongly connected:
– A directed graph is strongly connected if and only if, for each pair of
vertices v and w, there is a path from v to w.

• Strongly connected component:

– A strongly connected component of a digraph G
is a maximal strongly connected subgraph of G.

21
Strongly connected Components
and Equivalence Relations
• Strongly Connected Components may be
defined in terms of an equivalence relation,
S, on the vertices
– vSw iff there is a path from v to w and
– a path from w to v
• Then, a strongly connected component
consists of one equivalence class, C, along
with all edges vw such that v and w are in
C. 22
 Condensation graph
– The strongly connected components of a digraph can
each be collapsed to a single vertex yielding a new
digraph that has no cycles.
• Condensation graph:
– Let S1,S2,...Sp be the strong components of G.
– The condensation graph of G denoted as G, is the
digraph G = (V',E'),
– where V' has p elements s1,s2,...sp and
– sisj is in E' if and only if ij and
– there is an edge in E from some vertex in Si to some
vertex in Sj.
23
 Condensation graph and its
strongly connected components
• Condensation Graph is acyclic.

24
 Examples

Graph with strongly connected

components marked

25
 Bi-connected components of an
Undirected graph
• Problem:
– If any one vertex (and the edges incident upon it) are removed from a
connected graph,
– is the remaining subgraph still connected?
• Biconnected graph: (No separation edge and separation vertex)
– A connected undirected graph G is said to be biconnected if it remains
connected after removal of any one vertex and the edges that are incident
upon that vertex. Separation edge is also called cut edge and separation
vertex is called cut vertex.
• Biconnected component:
– A biconnected component of a undirected graph is a maximal biconnected
subgraph, that is, a biconnected subgraph not contained in any larger
biconnected subgraph.
• Articulation point:
– A vertex v is an articulation point for an undirected graph G if there are
distinct vertices w and x (distinct from v also) such that v is in every path26
from w to x.
Bi-connected graph

27
Not a biconnected graph
 Articulation point
• An articulation point
of a graph is a vertex
v such that when we
remove v and all
edges incident upon
v , we break
a connected
component of the
graph into two or
more pieces.
• A connected graph
with no articulation
points is said to
be biconnected.
28
 Bi-connected components, e.g.
• Some vertices are in more than one component
(which vertices are these?)

29
Example

30
Example

1. {10-12, 12-13, 10-13}

2. {10-11}
3. {8-9}
4. {7-8}
5. {1-2}
6. {1-3, 1-6, 3-7, 5-7, 4-5,5-6, 4-6, }

31
Example

32
 Exercises

Draw a directed graph, having as its eight vertices the strings

’ape’, ’ate’, ’eat’, ’era’, ’pea’, ’rap’, ’rat’, and ’tea’, and including
an edge from word x to word y whenever the last two letters of x
are the same as the first two letters of y; for instance, you should
include an edge from ’ape’ to ’pea’.

Consider the vertices 1 to 10. An edge is created iff the sum of two
vertices are divisible by 4. Draw the graph and find the total
number of edges. 33
 Exercises
• Is the graph connected? If not identify the connected
components.

34
 Graphs
• Motivation and Terminology
• Representations
• Traversals
• Three Problems

35
 Adjacency Matrix

1 2 1 2 3 4 5
1 0 1 1 1 0
2 1 0 0 1 0
3 4 3 1 0 0 1 1
4 1 1 1 0 1
5 0 0 1 1 0
5

36
Adjacency Matrix

37
 Adjacency List

1 2 1 2 3 4

2 1 4

3 1 4 5
3 4
4 1 2 3 5

5 3 4
5

38
Adjacency List

39
Tradeoffs Between Adjacency
Lists and Adjacency Matrices
Comparison Winner (for worst case)
Faster to test if (x, y) exists? matrices: (1) vs. (V)
Faster to find vertex degree? lists: (1) vs. (V)
Less memory on sparse graphs? lists: (V+E) vs. (V2)
Less memory on dense graphs? matrices: (small win)
Edge insertion or deletion? matrices: (1) vs. (V)
Faster to traverse the graph? lists: (E+V) vs. (V2)
Better for most problems? lists
40
 Incidence matrix

1
-1

41
Try for this…
 Graph Squaring
The square of a directed graph G = (V, E) is the graph
G2 = (V, E2), such that (x, y)  E2 iff, for some z, both
(x, z) and (z, y)  E ; i.e., there is a path of exactly two
edges.

Try yourself….
Give efficient algorithms to square a graph on both
adjacency lists and matrices.

42
Example

43
 G2 with Adjacency Matrices
To discover whether there is an edge (x, y) in E2, we do
the following.

For each possible intermediate vertex z, we check

whether (x, z) and (z, y) exist in O(1); if so for any z,
mark (x,y) in E2.

Since there are O(V) intermediate vertices to check,

and O(V2) pairs of vertices to ask about, this takes
O(V3) time.
44
 G2 with Adjacency Lists
We use an adjacency matrix as temporary storage.

For each edge (x, z), we run through all the edges (z,y)
from z in O(V) time, updating the adjacency matrix for
edge (x,y). We convert back to adjacency lists at the end.

It takes O(VE) to construct the edges, and O(V2) to

initialize and read the adjacency matrix, for a total of
O((V+E)V). Since E+1  V (unless the graph is
disconnected), this is usually simplified to O(VE), and is
faster than the previous algorithm on sparse graphs. 45
 Exercises
• Write the adjacency matrix, incidence
matrix and adjacency list representation of
this graph

46
 Graphs
• Motivation and Terminology
• Representations
• Traversals
• Three Problems

47
 Traversing a Graph
One of the most fundamental graph problems is to traverse
every edge and vertex in a graph. Applications include:
· Printing out the contents of each edge and vertex.
· Counting the number of edges.
· Identifying connected components of a graph.
For correctness, we must do the traversal in a systematic
way so that we don't miss anything.
For efficiency, we must make sure we visit each edge at
most twice.
48
 Marking Vertices
The idea in graph traversal is that we mark each vertex
when we first visit it, and keep track of what is not yet
completely explored.
For each vertex, we maintain two flags:
· discovered - have we encountered this vertex before?
· explored - have we finished exploring this vertex?
We must maintain a structure containing all the vertices
we have discovered but not yet completely explored.
Initially, only a single start vertex is set to be discovered.
49
 Correctness of Graph Traversal

Every edge and vertex in the connected component is

eventually visited.

Suppose not, i.e. there exists a vertex which was unvisited

whose neighbor was visited. This neighbor will
eventually be explored so we would visit it….

50
 Traversal Orders
The order we explore the vertices depends upon the data structure
used to hold the discovered vertices yet to be fully explored:
· Queue - by storing the vertices in a first-in, first out (FIFO)
queue, we explore the oldest unexplored vertices first. Thus we
radiate out slowly from the starting vertex, defining a so-called
breadth-first search.
· Stack - by storing the vertices in a last-in, first-out (LIFO)
stack, we explore the vertices by constantly visiting a new
neighbor if one is available; we back up only when surrounded
by previously discovered vertices. This defines a so-called
depth-first search.

51
BFS(G,s)
BFS(G,s)
1.1. for
foreach
eachvertex
vertexuuininV[G]
V[G]–– {s}{s}
22 do color[u]white
docolor[u] white
33 d[u]
d[u]
44 [u]
[u]nilnil white: undiscovered
color[s]gray
55 color[s] gray gray: discovered
d[s]00
66 d[s] black: finished
77 [s][s]nil
nil
88 QQ
Q: a queue of discovered
99 enqueue(Q,s)
enqueue(Q,s) vertices
10 whileQQ
10 while color[v]: color of v
11
11 dodouudequeue(Q)
dequeue(Q) d[v]: distance from s to v
12 for [u]: predecessor of v
12 foreach
eachvvininAdj[u]
Adj[u]
13
13 do
doififcolor[v]
color[v]==white
white
14
14 then color[v]
thencolor[v]
gray
gray
15
15 d[v]d[u]
d[v] d[u]++
11
16
16 [v]
[v]uu
17
17 enqueue(Q,v)
enqueue(Q,v)
18
18 color[u]black
color[u] black
52
 Example (BFS)
r s t u
 0  

   
v w x y

Q: s
Order of visit:
0
s 53
 Example (BFS)
r s t u
1 0  

 1  
v w x y

Q: w r
Order of visit:
1 1
s, w, r 54
 Example (BFS)
r s t u
1 0 2 

 1 2 
v w x y

Q: r t x
Order of visit:
1 2 2
s, w, r, t, x 55
 Example (BFS)
r s t u
1 0 2 

2 1 2 
v w x y

Q: t x v
Order of visit:
2 2 2
s, w, r, t, x, v 56
 Example (BFS)
r s t u
1 0 2 3

2 1 2 
v w x y

Q: x v u
Order of visit:
2 2 3
s, w, r, t, x, v, u 57
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: v u y
Order of visit:
2 3 3
s, w, r, t, x, v, u, y 58
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: u y
Order of visit:
3 3
s, w, r, t, x, v, u, y 59
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: y
Order of visit:
3
s, w, r, t, x, v, u, y 60
 Example (BFS)
r s t u
1 0 2 3

2 1 2 3
v w x y

Q: 
Order of visit:
s, w, r, t, x, v, u, y 61
 Example (BFS)
r s t u
T T
1 0 2 3
T
T T C C

2 1 2 3
T T
v w x y

BF Tree
BFS traversal:
s, w, r, t, x, v, u, y 62
 Analysis of BFS
• Initialization takes O(V).
• Traversal Loop
– After initialization, each vertex is enqueued and
dequeued at most once, and each operation takes O(1).
So, total time for queuing is O(V).
– The adjacency list of each vertex is scanned at most
once. The sum of lengths of all adjacency lists is (E).
• Summing up over all vertices => total running time
of BFS is O(V+E), linear in the size of the
adjacency list representation of graph.

63
BFS- Example 2

64
BFS- Example 2

65
BFS- Example 2

BFS tree
C C

BFS traversal:
1, 2, 5, 3, 6, 4, 7
66
BFS- Example 2

67
Exercise- Find the BFS tree and
the traversal
D
G
B J
H
E K
C
I
A F
L
68
 Depth-first Search (DFS)
• Explore edges out of the most recently discovered
vertex v.
• When all edges of v have been explored, backtrack to
explore other edges leaving the vertex from which v
was discovered (its predecessor).
• “Search as deep as possible first.”
• Continue until all vertices reachable from the original
source are discovered.
• If any undiscovered vertices remain, then one of them
is chosen as a new source and search is repeated from
that source.
69
 Depth-first Search
• Input: G = (V, E), directed or undirected. No source
vertex given!
• Output:
– 2 timestamps on each vertex. Integers between 1 and 2|V|.
• d[v] = discovery time (v turns from white to gray)
• f [v] = finishing time (v turns from gray to black)
– [v] : predecessor of v = u, such that v was discovered during
the scan of u’s adjacency list.
• Uses the same coloring scheme for vertices as BFS.

70
 Pseudo-code
DFS(G)
DFS(G) DFS-Visit(u)
DFS-Visit(u)
1.1. for
foreach vertexuuV[G]
eachvertex V[G] color[u]
1.1. color[u] GRAY 
GRAY White
Whitevertex
vertexuu
2.2. do color[u]
docolor[u] white
white has
hasbeenbeendiscovered
discovered
3.3. [u]
[u] NIL
NIL time
2.2. time time
time++11
time
4.4. time 00 3.3. d[u]
d[u] time
time
5.5. for
foreach vertexuuV[G]
eachvertex V[G] 4.4. for eachvvAdj[u]
foreach Adj[u]
6.6. do
doififcolor[u]
color[u]==white
white 5.5. do
doififcolor[v]
color[v]==WHITE
WHITE
7.7. then
thenDFS-Visit(u)
DFS-Visit(u) 6.6. then[v]
then [v]uu
7.7. DFS-Visit(v)
DFS-Visit(v)
8.8. color[u]
color[u] BLACK 
BLACK Blacken
Blackenu;u;
Uses a global timestamp time. ititisisfinished.
finished.
9.9. f[u]
f[u] time
time time
time++11

71
Example (DFS)
u v w
1/

x y z

72
Example (DFS)
u v w
1/ 2/

x y z

73
Example (DFS)
u v w
1/ 2/

3/
x y z

74
Example (DFS)
u v w
1/ 2/

4/ 3/
x y z

75
Example (DFS)
u v w
1/ 2/
B

4/ 3/
x y z

76
Example (DFS)
u v w
1/ 2/
B

4/5 3/
x y z

77
Example (DFS)
u v w
1/ 2/
B

4/5 3/6
x y z

78
Example (DFS)
u v w
1/ 2/7
B

4/5 3/6
x y z

79
Example (DFS)
u v w
1/ 2/7
F B

4/5 3/6
x y z

80
Example (DFS)
u v w
1/8 2/7
F B

4/5 3/6
x y z

81
Example (DFS)
u v w
1/8 2/7 9/
F B

4/5 3/6
x y z

82
Example (DFS)
u v w
1/8 2/7 9/
F B C

4/5 3/6
x y z

83
Example (DFS)
u v w
1/8 2/7 9/
F B C

4/5 3/6 10/

x y z

84
Example (DFS)
u v w
1/8 2/7 9/
F B C

4/5 3/6 10/ B

x y z

85
Example (DFS)
u v w
1/8 2/7 9/
F B C

4/5 3/6 10/11 B

x y z

86
 Example (DFS)
u v w
1/8 2/7 9/12
F B C

4/5 3/6 10/11 B

x y z

DFS traversal:
u, v, y, x, w, z
87
 Analysis of DFS
• Loops on lines 1-2 & 5-7 take (V) time, excluding time
to execute DFS-Visit.
• DFS-Visit is called once for each white vertex vV
when it’s painted gray the first time. Lines 3-6 of DFS-
Visit is executed |Adj[v]| times. The total cost of
executing DFS-Visit is vV|Adj[v]| = (E)
• Total running time of DFS is (V+E).

88
 DFS – Example 2

DFS traversal: DFS traversal: DFS traversal:

1 1, 2, 1, 2, 6
89
 DFS – Example 2

DFS traversal: DFS traversal: DFS traversal:

1, 2, 6 1, 2, 6, 4 1, 2, 6, 4
90
 DFS – Example 2

DFS traversal: DFS traversal: DFS traversal:

1, 2, 6, 4 1, 2, 6, 4, 5 1, 2, 6, 4, 5

91
 DFS – Example 2

DFS traversal: DFS traversal: DFS traversal:

1, 2, 6, 4, 5, 3 1, 2, 6, 4, 5, 3, 7 1, 2, 6, 4, 5, 3, 7

92
DFS – Example 2

DFS traversal:
1, 2, 6, 4, 5, 3, 7
93
DFS – Example 2

DFS traversal:
1, 2, 6, 4, 5, 3, 7
94
Example 3 – Identify the edges

S, 1, 2, 3, 4, 5, 6, 7
95
Exercise – Perform DFS
D
G
B J
H
E K
C
I
A F
L
96
 Directed Graph DFS trees
• Things are a bit more complicated
– Forward edges (ancestor to descendant)
– Cross Edges
• Not from an ancestor to a descendant
• Parenthesis structure still holds
– The discovery and finishing times of nodes in a
DFS tree have a parenthesis structure
• Can create a forest of DFS trees

97
 Classification of Edges
• Tree edge: in the depth-first forest. Found by exploring
(u, v).
• Back edge: (u, v), where u is a descendant of v (in the
depth-first tree).
• Forward edge: (u, v), where v is a descendant of u, but
not a tree edge.
• Cross edge: any other edge. Can go between vertices in
same depth-first tree or in different depth-first trees.

In
In DFS
DFS of
of an
an undirected
undirected graph,
graph, we
we get
get only
only tree
tree and
and
back
back edges.
edges. No
No forward
forward or
or cross
cross edges.
edges.

98
Exercises

99
 Graphs
• Motivation and Terminology
• Representations
• Traversals
• Three Problems

100
 Bipartite Graph?

Give an efficient algorithm to determine if a graph is

bipartite. (Bipartite means that the graph can be colored
with 2 colors such that all edges connect vertices of
different colors. )

101
 Cycle?
Give an O(V) algorithm to determine if an undirected
graph contains a cycle.

Note: Full traversal by BFS and DFS both take O(V+E)

time.

102
 Topological Sorting?
• A directed acyclic graph (DAG) is a directed graph with no
directed cycles.
• A topological sort is an ordering of nodes where all edges go
from left to right.
• How can BFS or DFS help us topologically sort a directed graph
(or determine the graph is not a DAG)?
A

B C A C F B D E

D E F 103
 DAGs and Topological Ordering
• A directed acyclic graph (DAG) is a D E
digraph that has no directed cycles
• A topological ordering of a digraph is B
a numbering
v1 , …, vn C
of the vertices such that for every edge A DAG G
(vi , vj), we have i < j
• Example: in a task scheduling digraph, v4 v5
a topological ordering a task sequence D E
that satisfies the precedence v2
constraints
B
Theorem v3
A digraph admits a topological
v1 C
ordering if and only if it is a DAG Topological
A
ordering
104 of
G
Example 1 – Topological
Ordering

105
Example 1

106
Example 1

107
Example 1

108
Algorithm

109
Algorithm

110
Example 2 - Topological Sort
C

G A B

D E

H 111
Example 2 - Topological Sort

112
Example 2 - Topological Sort

113
Example 2 - Topological Sort

114
Example 2 - Topological Sort

115
Example 2 - Topological Sort

116
Example 2 - Topological Sort
(Alternate Way)
C

G A B

D E

H 117
C
Topological Sort: DFS
dfs(A)

G A B

D E

118
C
Topological Sort: DFS
dfs(A)
dfs(D)

G A B

D E

119
C
Topological Sort: DFS
dfs(A)
dfs(D)
dfs(E)

G A B

D E

120
C
Topological Sort: DFS
dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B

D E

121
C
Topological Sort: DFS dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B dfs(H)

D E

122
C
Topological Sort: DFS
dfs(A)
dfs(D)
dfs(E)
dfs(F)
G A B

D E

H
7

123
C
Topological Sort: DFS
dfs(A)
dfs(D)
dfs(E)

G A B

D E

6
H
7

124
C
Topological Sort: DFS
dfs(A)
dfs(D)

G A B

D E
5

6
H
7

125
C
Topological Sort: DFS
dfs(A)
dfs(D)

G A B

D E
5

6
H
7

126
C
Topological Sort: DFS
dfs(A)

G A B

D E
4 5

6
H
7

127
C
Topological Sort: DFS
dfs(A)

G A B

D E
4 5

6
H
7

128
C
Topological Sort: DFS

G A 3 B

D E
4 5

6
H
7

129
C
Topological Sort: DFSdfs(B)

G A 3 B

D E
4 5

6
H
7

130
C
Topological Sort: DFSdfs(B)

G A 3 B

D E
4 5

6
H
7

131
C
Topological Sort: DFS

G A 3 B 2

D E
4 5

6
H
7

132
C
Topological Sort: DFS dfs(C)

G A 3 B 2

D E
4 5

6
H
7

133
C
Topological Sort: DFS dfs(C)

G A 3 B 2

D E
4 5

6
H
7

134
C
Topological Sort: DFS dfs(C)

G A 3 B 2

D E
4 5

6
H
7

135
C
Topological Sort: DFS dfs(C)

G A 3 B 2

D E
4 5

6
H
7

136
C
Topological Sort: DFS dfs(C)
dfs(G)

G A 3 B 2

D E
4 5

6
H
7

137
C
Topological Sort: DFS dfs(C)

G 1 A 3 B 2

D E
4 5

6
H
7

138
0 C
Topological Sort: DFS

G 1 A 3 B 2

D E
4 5

6
H
7

139
0 C
Topological Sort: DFS

G 1 A 3 B 2

D E
4 5

6
H
7

Topological order: C G B A D E140F H

Exercise – Find the Topological order

141