Data Structure Algorithms

and Applications
CT-157

Course Instructor
Engr. Vanesh Kumar
Graphs
 Introduction
• Graphs represent the • Each node represents an item
relationships among data items • Each edge represents the
• A graph G consists of relationship between two items
• A set V of Nodes (vertices)
• A set E of Edges: each edge
connects two nodes
node

edge
Introduction
• Graphs are a generalization of trees
• Nodes or vertices
• Edges or arcs
A
• Two kinds of graphs B C
• Directed
• Undirected D E

F
Undirected graph G

Directed graph
 Daily Life Examples of Graph
Molecular Structure Computer Network

H Server 1 Terminal 1

H C H
Terminal 2
H Server 2

Other examples: electrical and communication networks, airline routes, flow chart,
graphs for planning projects
Introduction: Formal Definition
• A graph G = (V,E) is composed of:
V: set of vertices
E: set of edges connecting the vertices in V
• Each edge is a pair (v,w) where v, w  V

v
(v, w)

w
Example of Graph
a b

d e

V= {a,b,c,d,e}
E= {(a,b),(a,c), (a,d), (b,e),(c,d),(c,e), (d,e)}
Introduction: Formal Definition
• A directed graph, or digraph, is a graph in which the
edges are ordered pairs
• (v, w) ≠ (w, v)
• An undirected graph is a graph in which the edges are
unordered pairs
• (v, w) == (w, v)
Introduction: Directed Graphs
• In a directed graph, the edges are arrows.
• Directed graphs show the flow from one node to another and not
vise versa.
Introduction: Undirected Graphs
• In a Undirected graph, the edges are lines.
• UnDirected graphs show a relationship between two
nodes.
Terminology

• In the directed graph above, b is adjacent to a

because (a, b)  E. Note that a is not
adjacent to b.
• A is a predecessor of node B
• B is a successor of node A
• The source of the edge is node A, the target is
node B
Terminology

• In the undirected graph above, a and b are

adjacent
because (a,b)  E. a and b are called
neighbors.

Adjacent vertices: Two vertices in a graph that

are connected by an edge.
Terminology

• A path is a sequence of vertices w1, w2,…wn such that (wi,

wi+1)  E, 1 <= i < n, and each vertex is unique except that
the path may start and end on the same vertex
• The length of the path is the number of edges along the
path
• The length can be Zero for the case of a single vertex.
Terminology

• An acyclic path is a path which does not

follow a sequence.
• A cyclic path is a path such that
• There are at least two vertices on the path
• w1 = wn (path starts and ends at same vertex)
• And also maintains the sequence
Test Your Knowledge
Cyclic or Acyclic?
Terminology
• A directed graph that has no cyclic paths is
called a
DAG (a Directed Acyclic Graph).
• An undirected graph that has an edge between
every pair of vertices is called a complete
graph.

Note: A directed graph can also be

a complete graph; in that case, there
must be an edge from every vertex
to every other vertex.
Test Your Knowledge
Complete, or “Acomplete” (Not Complete)
Test Your Knowledge
Complete, or “Acomplete” (Not Complete)
Terminology
• An undirected graph is connected if a path
exists between any two vertex

• A directed graph is strongly connected if a

path exists from every vertex to every other
vertex

• A directed graph is weakly connected if a

path exists from every vertex to every other
vertex, disregarding the direction of the
edge
Terminology
• A graph is known as a weighted graph if a
weight or metric is associated with each edge.
Terminology
- A cyclic graph contains at least one cycle

- An acyclic graph does not cycles

ontain any c

cyclic graph acyclic graph

Terminology
 The degree of a vertex is the number of edges incident to that vertex
 For directed graph,
 the in-degree of a vertex v is the number of edges that have v
as the head
 the out-degree of a vertex v is the number of edges that have v as
the tail

 if di is the degree of a vertex i in a graph G with n vertices and e edges,

the number of edges is
n 1
e  (  di ) / 2
0
Adjacent
Two nodes u and v are said to be adjacent if (u, v)  E

v
(u, v)
u
w
u and v are adjacent
v and w are not adjacent
Path and Simple path
• A path from v1 to vk is a sequence of nodes v1, v2, …, vk
that are connected by edges (v1, v2), (v2, v3), …, (vk-1, vk)
• A path is called a simple path if every node appears at most
once.
v2 v3
v1

- v2, v3, v4, v2, v1 is a path

- v2, v3, v4, v5 is a path, v4 v5
also it is a simple path
Cycle and Simple cycle
• A cycle is a path that begins and ends at the same node
• A simple cycle is a cycle if every node appears at most once,
except for the first and the last nodes

v2
v1 v3

- v2, v3, v4, v5 , v3, v2 is a cycle v4 v5

- v2, v3, v4, v5 is a cycle,
it is also a simple cycle
Connected Graph
A graph G is connected if there exists path between every pair of
distinct nodes; otherwise, it is disconnected

v2
v1 v3

v4 v5

This is a connected graph because there

exists path between every pair of nodes
Example of Disconnected Graph

v1 v3 v7 v8
v2
v4 v5
v6 v9

This is a disconnected graph because there does not exist

path between some pair of nodes, says, v1 and v7
Connected Component
If a graph is disconnect, it can be partitioned into a number of
graphs such that each of them is connected. Each such graph is
called a connected component.

v2 v7 v8
v1 v3

v4 v5
v6 v9
Complete Graph

A graph is complete if each pair of distinct nodes has an edge

Complete graph Complete graph

with 3 nodes with 4 nodes
Subgraph
A subgraph of a graph G =(V, E) is a graph H = (U, F)
such that U  V and F  E

v2 v2
v1 v3 v3

v4 v5 v4 v5

G H
Complete Graph
A complete graph is a graph that has the maximum
number of edges

 for undirected graph with n vertices, the maximum

number of edges is n(n-1)/2

 for directed graph with n vertices, the maximum

number of edges is n(n-1)

Complete Graph

No.of edges = n(n-1)/2 No.of edges = n(n-1)/2 No.of edges = n(n-1)

= 4*3/2 = 7*6/2 = 3*2
= 12/2 = 42/2 =6
=6 = 21
Multigraph
• A graph cannot have duplicate edges
• Multigraph allows multiple edges and self edge (or loop)

• Loops: edges that connect a vertex to itself

Self edge Multiple edge

Terminology
• A vertex with degree one is called pendent vertex or end
vertex.
• A vertex with degree zero and hence has no incident edges
is called an isolated vertex.

A V1

B
Isolated vertex
Pendent vertex

In the undirected graph vertex v3 has the degree 3 And vertex

v2 has the degree 2
Degree - Graph
Degree - digraph
Property of Graph
• A undirected graph that is connected and has no
cycle is a tree.

• A tree with n nodes have exactly n-1 edges.

• A connected undirected graph with n nodes must

have at least n-1 edges.
Tree
A tree is a graph that is

 connected

 acyclic.
Tree & Forest…
• tree - connected graph without cycles
• forest - collection of trees

tre e

tre e

forest

tree

tree
 Isomorphic Graph
• Isomorphism
– Two graphs are isomorphic, if they are structurally identical,
which means that they correspond in all structural details.
– Formal vertex-to-vertex and edge–to-edge correspondence is
called isomorphism.

– Two graph are said to be isomorphic if

 They have the same no of vertices.
 They have the same number of edges.
 They have an equal number of vertices with a
given degree.
Verifying Isomorphic Graph

Vertices(A) : a b c d e

Vertices(B): q p r s t
Degree of 2 3 3 3 1
vertices:
Edges(A): e1 e2 e3 e4 e5 e6
Edges(B): e’1 e’4 e’3 e’2 e’5 e’6
Examples for non-isomorphic graphs

1st graph has more edges than 2nd

Examples for non-isomorphic graphs

2nd graph has vertex of degree 1, 1st graph doesn't.

Examples for non-isomorphic graphs

1st graph has 2 degree-1 vertices, 4 degree-2 vertex

and 2 degree-3 vertices.
2nd graph has 3 degree-1 vertices, 3 degree-2 vertex
and 3 degree-3 vertices.
 Labeled & Unlabeled Graph
• A graph G is called a labeled graph if its edges and/or vertices
are assigned some data.

• A graph labeling is the assignment of labels, traditionally

represented by integers, to the edges or vertices, or both, of a
graph.

• If the edge e is assigned a non-negative number then it is called

the weight or length of the edge e.
 Labeled & Unlabeled Graph
• Vertex-labeled graph
If all the vertices in a graph are given a label then it is vertex-
labeled graph

• Edge-labeled graph
If all the Edges in a graph are given a label then it is Edge-
labeled graph
Representation of Graph
Following are the representation of agraph
• Adjacency Matrix
• Represent a graph using a two-dimensional array
• Adjacency List
• Represent a graph using n linked lists where n is the number of
vertices

There are other representations also like, Incidence Matrix and

Incidence List.
The choice of the graph representation is situation specific. It
totally depends on the type of operations to be performed and
ease of use.
Adjacency Matrix

• Adjacency Matrix is a 2D array of size V x V where V is the

number of vertices in a graph.

• Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that

there is an edge from vertex i to vertex j.
• Adjacency matrix for undirected graph is always symmetric.

• Adjacency Matrix is also used to represent weighted graphs. If

adj[i][j] = w, then there is an edge from vertex i to vertex j with
weight w.
Adjacency Matrix
Adjacency List
• An array of linked lists is used.
• Size of the array is equal to number of vertices.
• Let the array be array[].
• An entry array[i] represents the linked list of vertices adjacent to
the ith vertex.

• This representation can also be used to represent a weighted

graph.
• The weights of edges can be stored in nodes of linked lists.
Adjacency List
• Following is adjacency list representation of the above graph.
 Node Adjacency List

A B,C, D
B C
C
D C,E
E C

a) Graphs G
b) Adjacency lists of G
Adjacency matrix for directed graph
Matrix[i][j] = 1 if (vi, vj)E
0 if (vi, vj)E
1 2 3 4 5
v1 v2 v3 v4 v5
v2 1 v1 0 1 0 0 0
v1 v3
2 v2 0 0 0 1 0
3 v3 0 1 0 1 0
v4 v5 4 v4 0 0 0 0 0

G 5 v5 0 0 1 1 0
Adjacency matrix for weighted undirected graph
Matrix[i][j] = w(vi, vj) if (vi, vj)E or (vj, vi)E
∞ otherwise

1 2 3 4 5
v2 v1 v2 v 3 v4 v5
v1 2 v3
5 1 v1 ∞ 5 ∞ ∞ ∞
4 3
7 2 v2 5 ∞ 2 4 ∞
v4 8
v5 3 v3 0 2 ∞ 3 7
4 v4 ∞ 4 3 ∞ 8
G 5 v5 ∞ ∞ 7 8 ∞
Adjacency list for directed graph

v2 1 v1  v2
v1 v3
2 v2  v4
3 v3  v2  v4
v4 v5
4 v4
G 5 v5  v3  v4
 Adjacency list for weighted undirected graph

v1 
v2 1 v2(5)
v1 5 2 v3 2 v2  v1(5)  v3(2)  v4(4)
4 3 3 v3  v2(2)  v4(3)  v5(7)
7
4 v4  v2(4)  v3(3)  v5(8)
v4 8 v5
5 v5  v3(7)  v4(8)

G
Pros & Cons
• Adjacency matrix
 Allows us to determine whether there is an edge from node i to node j in O(1) time
 Adjacency matrix consumes huge amount of memory for storing big graphs.
• Adjacency list
 Allows us to find all nodes adjacent to a given node j efficiently in O(1) time
 Adjacent list allows us to store graph in more compact form, than adjacency matrix

In General,
• Adjacency matrix is good for dense graphs.
• Adjacency lists is good for sparse graphs and also for changing the no of
nodes.
Dense Graphs and Sparse Graphs
• Dense graph is a graph in which the number of edges is close
to the maximal number of edges.
• The opposite, a graph with only a few edges, is a sparse
graph.

Dense Graph Sparse Graph

Uses For Graphs
Uses for Graphs
• Computer network:
The set of vertices V represents the set of computers in
the network. There is an edge (u, v) if and only if there is a
direct communication link between the computers
corresponding to u and v.

• Two-Player Game Tree:

All of the possibilities in a board game like chess can be
represented in a graph. Each vertex stands for one possible
board position. (For chess, this is a very big graph!)
Social Media (Facebook)
Websites
Intercity Road Network
 Applications of Graph
CS16
• electronic circuits

•• networks (roads, flights, communications)

JFK

LAX STL
HNL
DFW
FTL
Solving a simple problem with Graph
• A network of computers can be represented By a graph, with
each vertex representing One of the machines in the
network, and
• an Edge representing a communication wire Between the two
machines.

• The question of whether one machine can send a message

to another machine boils down to whether the corresponding
vertices are Connected by a path
 Solving a simple problem with Graph
V0 to V3 = 1
V3 to V1 = 3
V1 to V2 = 2
Total 6

• Each edge has a NON-Negative Integer value attached to

it called the weight or cost of the edge
• The path with the lowest cost is called the Shortest path
Graphs Traversal
• To traverse a tree, we use tree traversal algorithms like;
pre-order, in-order, and post-order to visit all the nodes in a tree

• Similarly, graph traversal algorithm tries to visit all the nodes it

can reach.

• If a graph is disconnected, a graph traversal that begins at a

node v will visit only a subset of nodes, that is, the connected
component containing v.
Graphs Traversal
• Problem: Search for a certain node or traverse all nodes in the
graph

• Depth First Search

 Once a possible path is found, continue the search until the end of the
path
 Travel as far as you can down a path

• Breadth First Search

 Start several paths at a time, and advance in each one step at a time
 Look at all possible paths at the same depth before you go at a
deeper level
Depth-First Search (DFS)
• DFS strategy looks similar to pre-order.
 From a given node v, it first visits itself.
 Then, recursively visit its unvisited neighbours one by
one.
• DFS can be defined recursively as follows.

 Strategy in General: Expand deepest unexpanded node

 DFS Example
Start from v3
1
v3
2
v2 v2
v1 v3
3 4
v1 v4
v4 v5
5
G v5
Non-recursive DFS example
visit stack
v3 v3
v2 v3, v2
v2
v1 v3, v2, v1
v3
backtrack v3, v2 v1
v4 v3, v2, v4
v5 v3, v2, v4 , v5 v4 v5
backtrack v3, v2, v4
backtrack v3, v2
backtrack v3 G
backtrack empty
Breadth-First Search (BFS)
• BFS strategy looks similar to level-order.
 From a given node v, it first visits itself.
 Then, it visits every node adjacent to v before visiting any other
nodes.
1. Visit v
2. Visit all v’s neigbours
3. Visit all v’s neighbours’ neighbours
…

• Similar to level-order, BFS is based on a queue.

 Strategy in General: Expand shallowest unexpanded node

 BFS Example
Start from v5
1
v5
v2
v1 v3 2 3
v3 v4

v4 v5 4
v2
G
5
v1
 Non-recursive BFS example
Start from v5 Visit Queue
(front to back)

v2 v5 v5
v1 v3 empty
v3 v3
v4 v3, v4

v4 v5 v4
v2 v4, v2
G v2
empty
v1 v1
empty
Graphs Traversal
In general:
Both traversal algorithms
1. Start at one vertex of a graph
2. Process the information contained at that vertex
3. Move along an edge to process a neighbor

 DFS can be implemented efficiently using a Stack

 BFS can be implemented efficiently using a Queue
Graphs Traversal
• The traversal algorithm should be careful that it doesn’t enter
a “Repetitive Cycle”. Therefore we will mark each vertex as it
is processed..
• When the traversal finishes, all of the vertices that can be
reached from the start vertex have been processed.
• Some of the vertices may not be processed because there is
NO PATH from the START VERTEX
 DFS vs. BFS
DFS Process
F B A start
E
G D C
destination

D Call DFS on D Return

C DFS on C
B DFS on B B B to call on B
A DFS on A A A A

G Call DFS on G
D
found destination - done!
B
Path is implicitly stored in DFS recursion Path is:
A
A, B, D, G
 DFS vs. BFS
BFS Process
F B A start
E
G D C
destination

rear front rear front rear front rear front

A B D C D
Initial call to BFS on A Dequeue A Dequeue B Dequeue C
Add B Add C, D Nothing to add
Add A to queue

rear front
G found destination - done!
Dequeue D
Path must be stored separately
Add G
 Hamiltonian circuit
• Hamiltonian paths and circuits are named after the Mathematician ,William
Rowan Hamilton.
• A Hamiltonian circuit in a connected graph is defined as a closed walk that
traverses every vertex of G exactly once, also called Hamiltonian cycles.
• It is called as circuit if it includes every vertex of G. If any edge is removed
then it is Hamiltonian path.

Hamiltonian circuit: {v1,v3,v4,v2,v6,v5,v1}

• The above is a Hamiltonian circuit as each and

every vertex is traversed once
• And completes the circuit by ending in starting
point.
 Hamiltonian circuit
• A Hamiltonian path or traceable path is a path that visits each vertex exactly
once. Its also called as a traceable graph.

• A graph is Hamiltonian-connected if for every pair of vertices there is a

Hamiltonian path between the two vertices.

Hamiltonian path
 Summary
• Graphs are one of the most important non-linear data structures.
• A graph is a representation of relation

• Vertices represent elements and edges represent relationships

• In other words, a graph is a collection of nodes (vertices) and arcs joining

pair of the nodes (edges)

• Graphs are classified as directed and undirected graphs.

• In an undirected graph, an edge is a set of two vertices where order does
not make any relevance, whereas in a directed graph, an edge is an ordered
pair.
 Summary
• Graphs are implemented using an array or a linked list representation

• An adjacency list is a data structure for representing a graph by keeping a list

• of the neighbour vertices for each vertex

• An adjacency matrix is a data structure for representing a graph as a Boolean

matrix where 0 means no edge and 1 corresponds to an edge