12-09-2023

Graph Representation
Bachelor of Technology
CSE (AIML)/ICT
• Graph
Adjacency List
Space – 𝜃(𝑉 + 𝐸)
• A non-linear data structure denoted by 𝐺 𝑉, 𝐸 .
• 𝑉 - set of vertices/nodes
Analysis and Design of Algorithms • 𝐸 – set of edges
Module 2
• Representing/storing graphs in memory.
Elementary Graph Algorithms
Adjacency
Adjacency List
Matrix Graph
Dr. Anuj Kr. Singh Representation
Associate Professor Two Ways Adjacency Matrix
Sparse Graphs Dense Graphs
Computer Science & Engineering |𝐸| ≪ |𝑉| |𝐸| ≅ |𝑉| Space – 𝜃(𝑉 )

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 2

Adjacency List Representation Adjacency List Representation

• The adjacency-list representation of a graph 𝐺 𝑉, 𝐸 consists of an array 𝐴𝑑𝑗 of |𝑉| lists, one for Example 1 (UDG) Example 2 (DG)
each vertex in 𝑉 .

• For each 𝑢 ∈ 𝑉 , the adjacency list 𝐴𝑑𝑗(𝑢) contains all the vertices such that there is an edge
(𝑢, 𝑣) ∈ 𝑉.

• That is, 𝐴𝑑𝑗(𝑢) consists of all the vertices adjacent to 𝑢 in 𝐺.

• 𝑨𝒅𝒋 is actually an array of |𝑽| lists corresponding to each vertex in the graph.

Size of Adj Size of Adj

01 𝟐 |𝑬| 01 |𝑬|
List (UDG) List (DG)

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 3 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 4
 12-09-2023

Adjacency Matrix Representation Adjacency List Representation

• For the adjacency-matrix representation of a graph 𝐺 𝑉, 𝐸 , we assume that the vertices are Example 1 (UDG) Example 2 (DG)
numbered 1, 2, … … . , |𝑉| in some arbitrary manner.

• Then the adjacency-matrix representation of a graph 𝐺 𝑉, 𝐸 consists of a |𝑉| × |𝑉|matrix 𝐴 =

(𝑎 ) such that

01 For UDG 𝑨 = 𝑨𝑻 01 For DG 𝑨 ≠ 𝑨𝑻

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 5 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 6

Graph Searching Breadth First Search

• Searching a graph 𝐺(𝑉, 𝐸) means to BFS

(Breadth First Search) • Given a graph 𝐺(𝑉, 𝐸) and a distinguished source vertex 𝑠.
systematically follow the edges of the
Output – A Tree (BFT)
graph so as to visit each vertex of the • BFS systematically explores the edges of G to “discover” every vertex that is reachable from s.
graph.
• It also computes the distance (smallest number of edges) from s to each reachable vertex.

• Both BFS and DFS runs in θ(𝑉 + 𝐸) time. • It produces a “Breadth-First Tree (BFT)” with root s that contains all reachable vertices.

• For any vertex reachable from s, the simple path in the breadth-first tree from s to corresponds to
• BFS uses QUEUE a “shortest path” from s to in G, that is, a path containing the smallest number of edges.
• DFS uses STACK.
Graph Searching • The algorithm works on both directed and undirected graphs.
Two Algorithms DFS
(Depth First Search)
Output – A Forest (DFF)

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 7 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 8
 12-09-2023

Breadth First Search Breadth First Search

BFS (G) // G is the graph and s is the starting node BFS (G) // G is the graph and s is the starting node
1 for each vertex u ∈ V [G] - {s} 1 for each vertex u ∈ V [G] - {s}
2 do color[u] ← WHITE // color of vertex u 2 do color[u] ← WHITE // color of vertex u
Three Parameters
3 d[u] ← ∞ // distance from source s to vertex u 3 d[u] ← ∞ // distance from source s to vertex u
4 π[u] ← NIL // predecessor of u • Color [u] :Color of vertex u 4 π[u] ← NIL // predecessor of u
5 color[s] ← GRAY
• d[u] : distance from source s to vertex u 5 color[s] ← GRAY
• π[u] : predecessor of u
6 d[s] ← 0 6 d[s] ← 0
7 π[s] ← NIL 7 π[s] ← NIL
8 Q←Ø // Q is a FIFO - queue 8 Q←Ø // Q is a FIFO - queue
9 ENQUEUE(Q, s) 9 ENQUEUE(Q, s)
1
10 while Q ≠ Ø // iterates as long as there are gray vertices. Lines 10-18 10 while Q ≠ Ø // iterates as long as there are gray vertices. Lines 10-18
11 do u ← DEQUEUE(Q) 2 11 do u ← DEQUEUE(Q)
12 for each v ∈ Adj[u] 3 12 for each v ∈ Adj[u]
13 do if color[v] = WHITE // discover the undiscovered adjacent vertices White 13 do if color[v] = WHITE // discover the undiscovered adjacent vertices
14 then color[v] ← GRAY // enqueued whenever painted gray (Undiscovered) 14 then color[v] ← GRAY // enqueued whenever painted gray
15 d[v] ← d[u] + 1
Gray 15 d[v] ← d[u] + 1
(Discovered)
16 π[v] ← u 16 π[v] ← u
Black
17 ENQUEUE(Q, v) (Finished) 17 ENQUEUE(Q, v)
18 color[u] ← BLACK // painted black whenever dequeued 18 color[u] ← BLACK // painted black whenever dequeued
12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 9 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 10

Breadth First Search Depth First Search

• The strategy followed by depth-first search is, as its name implies, to search “deeper” in the graph
Example whenever possible.

• Depth-first search explores edges out of the most recently discovered vertex that still has
unexplored edges leaving it.

• Once all of the edges have been explored, the search “backtracks” to explore edges leaving the
vertex from which it was discovered.

• This process continues until we have discovered all the vertices that are reachable from the
original source vertex.

• The output of DFS is a Forest – Depth First Forest.

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 11 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 12
 12-09-2023

Depth First Search Depth First Search

DFS(G)
1 for each vertex u ∈ V [G] Three Parameters
2 do color[u] ← WHITE // color all vertices white, set their parents NIL • 𝐶𝑜𝑙𝑜𝑟 [𝑢] :Color of vertex u
Example 3 π[u] ← NIL • 𝜋[𝑢] : predecessor of u
4 me ← 0 // zero out time • 𝑡𝑖𝑚𝑒 : Global Variable
5 for each vertex u ∈ V [G] // call only for unexplored vertices
6 do if color[u] = WHITE // this may result in multiple sources
7 then DFS-VISIT(u)

DFS-VISIT(u)
1
1 color[u] ← GRAY ▹White vertex u has just been discovered.
2 me ← me +1 2
3 d[u] time // record the discovery time 3
4 for each v ∈ Adj[u] ▹Explore edge(u, v). White
5 do if color[v] = WHITE (Undiscovered)
Gray
6 then π[v] ← u // set the parent value
(Discovered)
7 DFS-VISIT(v) // recursive call Black
8 color[u] BLACK ▹ Blacken u; it is finished. (Finished)
9 f [u] ▹ me ← me +1
12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 13 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 14

Depth First Search Topological Sort

• A Topological Sort of a DAG G(V,E) is a linear ordering of all its vertices such that if G contains an
Two edge (u,v) then u appears before in the ordering.
Applications
• If the graph contains a cycle, then no linear ordering is possible.

Topological Strongly Connected • Used to order related events.

Sort Components

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 15 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 16
 12-09-2023

Topological Sort Strongly Connected Component

Example
• A strongly connected component of a directed graph G(V,E) is a maximal set of vertices C is a
subset of V[G] such that for every pair of vertices u and v in C, we have a path from both u to v
and v to u that is, vertices u and are reachable from each other.

Linearly
Ordered List
12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 17 12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 18

Strongly Connected Component

SCC

GT

12-09-2023 Dr. Anuj Kr. Singh, Associate Professor 19