Accredited with Grade A by NAAC
Accredited with Grade A by KCG
CE245 : Data Structure and Algorithms
Topic: Graph Data Structure
Prepared By,
Dr. Nikita Bhatt
Prof. Sarita Thummar
Graph
A graph G = (V,E) is composed of:
V: set of vertices
E: set of edges connecting the vertices in V
An edge e = (u,v) is a pair of vertices
a b V= {a,b,c,d,e}
E= {(a,b),(a,c),(a,d),
(b,e),(c,d),(c,e),
c (d,e)}
d e
2
Applications of Graph
Social Networks: Connecting friends on social media, where each user is a vertex, and
when users connect they create an edge.
Facebook, twitter, Instagram
3
Applications of Graph(continue)
Minimizing connection in IC: Integrated Circuits consists of millions of transistors,
which need to be connected. It is important to optimize these countless connections to
improve the performance of the chip. (MST)
Minimizing number of registers required for Code Generation- Graph Coloring
4
Applications of Graph(continue)
Topological ordering: Course Prerequisite Structure
https://slideplayer.com/slide/6918692/
5
Applications of Graph(continue)
Graph in Drug Discovery
Molecules are Graph.
Atoms as nodes, bonds as edges
Features such as atom type, charge, bond type…
6
Applications of Graph(Continue)
Graph in Drug Discovery
Interesting task is to predict whether the molecule is a potent drug.
• Can do binary classification on whether the drug will inhibit certain bacteria. (E.Coli)
• Train on a dataset for compounds where response is known.
• Once training is done, a model can be applied to any molecule.
• Select the top 100 candidates from GNN model.
• Provide that information to chemists
7
Applications of Graph(Continue)
Success Story: The most popularized success story of Graph Neural Network(GNN).
8
Applications of Graph(Continue)
Transportation maps (e.g. the ones found on Google Maps) naturally modelled as Graph.
Nodes could be intersections and edges could be roads. (Relevant node features: road
length, current speed, historical speeds)
9
Applications of Graph(Continue)
GNNs are a very hot research topic.
10
Terminology: Path
path:
3 2
sequence of vertices
v1,v2,. . .vk such that 3
consecutive vertices vi 3 3
and vi+1 are adjacent.
a b a b
c c
d e d e
abedc bedc
11
More Terminology
simple path: no repeated vertices
a b
bec
c
d e
• cycle: simple path, except that the last vertex is the same as
the first vertex
a b
a c da
c
d e
Even More Terminology
•connected graph: any two vertices are connected by some path
connected not connected
• subgraph: subset of vertices and edges forming a graph
• connected component: maximal connected subgraph. E.g., the graph below
has 3 connected components.
Types of Graph
1. Finite Graph: The graph G=(V, E) is called a finite graph if the
number of vertices and edges in the graph is limited in number.
Types of Graph
Infinite Graph:
The graph G=(V, E) is called a finite graph if the number of vertices
and edges in the graph is interminable.
Types of Graph
Trivial Graph:
A graph G= (V, E) is trivial if it contains only a single vertex and no
edges.
Types of Graph
Simple Graph:
If each pair of nodes or vertices in a graph G=(V, E) has only one
edge, it is a simple graph. As a result, there is just one edge linking
two vertices, depicting one-to-one interactions between two
elements.
Types of Graph
Multi Graph:
If there are numerous edges between a pair of vertices in a graph
G= (V, E), the graph is referred to as a multigraph. There are no self-
loops in a Multigraph.
Types of Graph
Null Graph:
It's a reworked version of a trivial graph. If several vertices but no
edges connect them, a graph G= (V, E) is a null graph
Types of Graph
Complete Graph:
If a graph G= (V, E) is also a simple graph, it is complete. Using the
edges, with n number of vertices must be connected. It's also
known as a full graph because each vertex's degree must be n-1.
Types of Graph
Psuedo Graph:
If a graph G= (V, E) contains a self-loop besides other edges, it is a
pseudograph.
Types of Graph
Regular Graph:
If a graph G= (V, E) is a simple graph with the same degree at each
vertex, it is a regular graph. As a result, every whole graph is a
regular graph.
Types of Graph
Weighted Graph:
A graph G= (V, E) is called a labeled or weighted graph because each
edge has a value or weight representing the cost of traversing that
edge.
Types of Graph
Directed Graph:
A directed graph also referred to as a digraph, is a set of nodes
connected by edges, each with a direction.
Types of Graph
Indirected Graph:
An undirected graph comprises a set of nodes and links connecting
them. The order of the two connected vertices is irrelevant and has
no direction. You can form an undirected graph with a finite number
of vertices and edges.
Types of Graph
Connected Graph:
If there is a path between one vertex of a graph data structure and
any other vertex, the graph is connected.
Types of Graph
Disconnected Graph:
When there is no edge linking the vertices, you refer to the null
graph as a disconnected graph ere is a pa
Types of Graph
Cyclic Graph:
If a graph contains at least one graph cycle, it is considered to be
cyclic.
Types of Graph
Acyclic Graph:
When there are no cycles in a graph, it is called an acyclic graph.
Types of Graph
Subgraph:
The vertices and edges of a graph that are subsets of another graph
are known as a subgraph.
Graph Representations
Adjacency Matrix
Adjacency Lists
Graphs: Adjacency Matrix
Example:
A 1 2 3 4
1
a
1
d 2
2 4
3
b c ??
3 4
32
Graphs: Adjacency Matrix
Example:
A 1 2 3 4
1
a
1 0 1 1 0
d 2 0 0 1 0
2 4
b c 3 0 0 0 0
3
In Degree and Out Degree
4 0 0 1 0
33
Graphs: Adjacency Matrix
How much storage does the adjacency matrix require?
Answer: O(V2)
The adjacency matrix is a sparse representation (number of edges is close to the
maximum number of edges)
• Usually too much storage for large graphs
• But can be very efficient for small graphs
Most large interesting graphs are sparse
• For this reason the adjacency list is often a more appropriate representation
34
Graphs: Adjacency List
Adjacency list: for each vertex v V, store a list of vertices adjacent to v
Example:
• Adj[1] = {2,3}
• Adj[2] = {3}
• Adj[3] = {} 1
• Adj[4] = {3}
2 4
Variation: can also keep a list of edges coming into vertex 3
35
0 0 4
2 1 5
1 2 3 6
3 7
0 1 2 3 0 1 2
1 0 2 3 1 0 3
2 0 1 3 2 0 3
3 0 1 2 3 1 2
G1 0
0 1
1 0 2 1
2
G3
2
An undirected graph with n vertices and e edges ==> n head nodes and 2e list nodes
Graph Searching
Given: a graph G = (V, E), directed or undirected
Goal: methodically explore every vertex and every edge
Ultimately: build a tree on the graph
• Pick a vertex as the root
• Choose certain edges to produce a tree
• Note: might also build a forest if graph is not connected
37
Review: Breadth-First Search
“Explore” a graph, turning it into a tree
• One vertex at a time
• Expand frontier of explored vertices across the breadth of the frontier
Builds a tree over the graph
• Pick a source vertex to be the root
• Find (“discover”) its children, then their children, etc.
38
Breadth-First Search: Example
r s t u
v w x y
39
Breadth-First Search: Example
r s t u
0
v w x y
Q: s
40
Breadth-First Search: Example
r s t u
1 0
1
v w x y
Q: w r
41
Breadth-First Search: Example
r s t u
1 0 2
1 2
v w x y
Q: r t x
42
Breadth-First Search: Example
r s t u
1 0 2
2 1 2
v w x y
Q: t x v
43
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2
v w x y
Q: x v u
44
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: v u y
45
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: u y
46
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: y
David Luebke
47
10/5/2023 47
Breadth-First Search: Example
r s t u
1 0 2 3
2 1 2 3
v w x y
Q: Ø
48
Breadth First Traversal
BFT(G, n)
{
for i = 1 to n do
visited i = 0;
for i = 1 to n do
if visited i = 0
then
BFS i ;
}
49
49
𝐁𝐅𝐒 𝐯 //The Graph G and array visited[] are global;
visited[] is initialized to ‘0’
{
u = v; visited v = 1;
repeat
{
for all vertices w adjacent to u do
{
if visited w == 0
{
add w to q;
visited w = 1;
}
}
if q is empty then return;
Delete the next element from q, add it to u;
}
}
50
50
Breadth-First Search: Properties
BFS calculates the shortest-path distance to the source node
• Shortest-path distance (s,v) = minimum number of edges from s to v, or if v not reachable from s
• Proof given in the book (p. 472-5)
BFS builds breadth-first tree, in which paths to root represent shortest paths in G
• Thus can use BFS to calculate shortest path from one vertex to another in O(V+E) time
51
Applications of BFS
Shortest path in a graph
Web Crawler
Social Network
Detecting a cycle in Undirected Graph
Broadcasting in a Network
52
52
Depth-First Search
Depth-first search is another strategy for exploring a graph
• Explore “deeper” in the graph whenever possible
• Edges are explored out of the most recently discovered vertex v that still has unexplored edges
• When all of v’s edges have been explored, backtrack to the vertex from which v was discovered
53
DFS Example
source
vertex
54
DFS Example
source
vertex
d f
1 | | |
| |
| | |
55
DFS Example
source
vertex
d f
1 | | |
2 | |
| | |
56
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | | |
57
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 | |
58
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | |
59
DFS Example
source
vertex
d f
1 | | |
2 | |
3 | 4 5 | 6 |
60
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
61
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 |
3 | 4 5 | 6 |
62
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |
3 | 4 5 | 6 |
What is the structure of the grey vertices?
What do they represent?
63
DFS Example
source
vertex
d f
1 | 8 | |
2 | 7 9 |10
3 | 4 5 | 6 |
64
DFS Example
source
vertex
d f
1 | 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
65
DFS Example
source
vertex
d f
1 |12 8 |11 |
2 | 7 9 |10
3 | 4 5 | 6 |
66
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 |
67
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|
68
DFS Example
source
vertex
d f
1 |12 8 |11 13|
2 | 7 9 |10
3 | 4 5 | 6 14|15
69
DFS Example
source
vertex
d f
1 |12 8 |11 13|16
2 | 7 9 |10
3 | 4 5 | 6 14|15
70
Depth First Traversal
DFT(v)
{
for i = 1 to n do
visited i = 0
for i = 1 to n do
{
if visited i == 0 then
DFS i ;
}
}
71
71
Depth First Search
DFS(v)
{
visited v = 1;
for each vertex w adjacent to v do
{
if visited w == 0 then
DFS w ;
}
72
72
Applications of DFS
Cycle Detection : (Find Back edge : An edge that is from a
node itself (self loop) or one of its ancestor)
Topological Sorting
To find strongly connected components
73
73
Gate 2003
Consider the following graph
Among the following sequences
I) a b e g h f II) a b f e h g III) a b f h g e IV) a f g h b e
Which are depth first traversals of the above graph?
(A) I, II and IV only (B) I and IV only (C) II, III and IV only (D) I, III and IV
only
Answer: (D)
74
Gate 2008
Consider the following sequence of nodes for the undirected graph given below.
abefdgc
abefcgd
adgebcf
adbcgef
A Depth First Search (DFS) is started at node a. The nodes are listed in the order
they are first visited. Which all of the above is (are) possible output(s)?
(A) 1 and 3 only (B) 2 and 3 only (C) 2, 3 and 4 only (D) 1, 2, and 3
Answer: (B)
75
75
Gate 2014
Suppose depth first search is executed on the graph below starting at some unknown
vertex. Assume that a recursive call to visit a vertex is made only after first checking that
the vertex has not been visited earlier. Then the maximum possible recursion depth
(including the initial call) is _________.
(A) 17 (B) 18 (C) 19 (D) 20
Answer: (C)
76
76
Gate 2006
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R.
Let discovery time d(u) represent the time instant when the vertex u is first visited,
and finish time f(u) represent the time instant when the vertex u is last visited.
Given that
d(P) = 5 units f(P) = 12 units
d(Q) = 6 units f(Q) = 10 units
d(R) = 14 unit f(R) = 18 units
which one of the following statements is TRUE about the graph
(A) There is only one connected component
(B) There are two connected components, and P and R are connected
(C) There are two connected components, and Q and R are connected
(D) There are two connected components, and P and Q are connected
Answer: (D)
77
77
