Chapter 6

Graph
 Introduction
• Data structure used to model a large variety
of data.
• Graph algorithms are useful in a huge
number of applications in computer science.
• Used in data storage
• Computer networks
FIGURE (a) A campus map as a graph;
(b) a subgraph
FIGURE Graphs that are (a) connected;
(b) disconnected; and (c) complete
May 30, 2021 5
May 30, 2021 6
 Examples of graph

May 30, 2021 7

• Many applications in the computer science
and mathematics have been written.
• Graph algorithms are used for searching the
data and finding the shortest path between
the nodes.
May 30, 2021 9
 Basic Concepts about Graphs
a) A set of entities called nodes (or vertices or
points).
b) A set of edges (or arcs or links) connecting the
vertices.
• A graph structure G is defined as G = (V, E)
where V is a set of vertices, E is a set of edges,
and each edge is formed from pair of distinct
vertices in V.
May 30, 2021 12
 Trees vs graphs
• Trees are special cases of graphs!!
• Graph does not have any root node like tree.
• Any node can be connected with any other
node.
• Nodes do not have any clear parent-child
relationship like in the tree.
• Instead nodes are called as neighbors if they
are connected by an edge.
• An edge E=( v1,v2) is said to point or traverse
from v1 to v2.
• The nodes are part of the graph structure.
• Nodes are external elements represented by
indices or references.
 Cycles and trees
• Graph with cycles: acyclic
• Directed Acyclic Graph
• Acyclic undirected graph (Undirected forest)
• Tree: undirected acyclic connected graph

May 30, 2021 16

• Complete graph: a graph in which every vertex
is directly connected to every other vertex

May 30, 2021 17

 Graph implementation
• Array-based implementation
– A1 array is used to represent the vertices
– A2 array (adjacency matrix) is used to
represent the edges
 Graph implementation
• Linked-list implementation
– Array is used to represent the vertices
– A list is used for each vertex v which contains the
vertices which are adjacent from v (adjacency list)
Linked-list implementation
 Representing graphs
• Adjacency matrix:
– When graph is dense
– |E| close to |V|2
• Adjacency lists:
– When graph is sparse
– |E| << |V|2

May 30, 2021 21

 Examples

May 30, 2021 22

May 30, 2021 23
May 30, 2021 24
Basic Terms and Terminologies
• Arc: Directed link between two nodes is
known as Arc.
• For example, the arc (v1,v2) traverse from tail
node v1 to head node v2.
• Edge: Undirected link between the nodes is
known as Edge.
• Path: A path is a sequence of consecutive
edges
• Length of the path is the number of edges
traversed.
Operations
• Adjacent (G, v1, v2): tests whether there is an
edge from node v1 to node v2 .
• Neighbors (G, v1): lists all nodes such that
there is an edge from v1 to v2.
• Add (G, v1, v2): adds to G the edge from v1 to
v2, if it is not there.
• Delete (G, v1, v2): removes the edge from v1 to
v2, if it is there.
• Get node value (G, v1): returns the value
associated with the node v1.
• Set node value (G, v1, a): sets the value
associated with the node v1 to a.
Types of Graphs
1) Undirected graph: The directions of edges
are not assigned.
2) Edge (v1,v2) is equivalent to edge (v2,v1)
• Directed graph: Each edge e in G is assigned a
direction.
• Each edge ‘e’ is identified with an ordered pair
(v1,v2) of nodes in G.
3) Weighted graphs: data information such as
cost or weight is associated to the traversal of
an edge.
• This is the extension of Undirected or Directed
graph operation.
4) Multigraph
• Graph with more than one edge between the
same two vertices.
• For example, there might be multiple flights
between two cities, occurring at different
times of the day.
• To distinguish between different nodes and
edges then we can associate labels with each
nodes and edges.
• If a label is associated with each nodes and
edges in a graph then such a graph is said to
be labeled.
6) Acyclic graph: It is defined as a graph with no
path that starts and ends at the same vertex.
• An acyclic undirected graphic is like a tree.
• Directed Acyclic graph (DAG) is a directed
graph with no path that starts and ends at the
same vertex.
• It is also known as oriented acyclic graph.
7) Graph with isolated vertices: Vertex is not
adjacent to any other vertices in a graph.
8) Null graph: A graph containing only isolated
vertices is called Null Graph.
9) Strongly connected graph: For each pair (v1,
v2) of nodes in G there is a path from v1 to v2
and there is also a path from v2 to v1.
• Whereas G is said to be unilaterally
connected graph if for any pair (u, v) of nodes,
there is a path from u to v or a path v to u.
Degree
• The degree of a vertex is the number of edges.
• In an undirected graph, the degree of a vertex
v is the number of edges connected to v.
• In a directed graph, the out-degree of a vertex
v is the number of edges leaving v, and its in-
degree is the number of edges ending at v.
Number of Edges
• If an edge e connects vertex v1 and v2, we
denote it as e= (v1, v2).
• If v1 = v2, e is called a self-loop.
May 30, 2021 41
• E= {(v1, v4 ), (v2, v1), (v1, v3 ), (v3, v2 ), (v5, v1 ),
(v5, v5 ), (v3, v2 ) }
• Where e1 = (v1, v4), e2 = (v2, v1), e3 = (v1, v3 ), e4
= (v2, v3 ), e5 =(v5, v1 ), e6= (v5, v5 ) and e7 =(v3,
v2 )
• From e3 and e7, v3 is common.
• In e3, v3 is the terminal vertex and it is initial
vertex of e7.
• Similarly, in e7 and e2, v2 is common.
• V5 exists a circular path.
 Matrix Representation of Graphs
Adjacency matrix
• Two-dimensional Boolean matrix to store the
information in the graph nodes.
• The rows and columns represent source and
destination.
• The values of matrix are either 0 or 1.
• Suppose if a graph G consists of v1 , v2 , v3 , v4 ,
v5 vertices then the adjacency matrix A = [aij]
of the graph G is the n x n matrix and can be
defined as:
• aij =1 if vi is adjacent to vj (i.e if there is an
edge between vi and vj) whereas aij =0 if there
is no edge between vi and vj.
May 30, 2021 46
May 30, 2021 47
May 30, 2021 48
• Figure: 5 vertices and 7 edges.
• V= {v1, v2, v3, v4, v5 }
• E= {(v2, v1), (v1, v3 ), (v3, v2 ) and so on
• Where e1 = (v1, v4), e2 = (v2, v1), e3 = (v1, v3 ), e4
=(v3, v2), e5 =(v5, v1 ), e6= (v5, v5 ), e7 =(v3, v2 )
• '1' is marked in a cell if there exists an edge
between two nodes.
• For example, since we have edge e1 from v1 to
v2, we mark a '1' in the cells indexed by v1 and
v2 otherwise it is 0.
• For a null graph, which consists of V vertices
but no edges, the adjacency matrix has all of
its entire elements as zero.
Incidence matrix
• It is a two-dimensional matrix, in which the
rows represent the vertices and columns
represent the edges.
• The entries in an array indicate if both are
related to each other through edges.
• The values of the matrix are given as -1, 0, or
1.
• If the kth edge is (vi, vj ) then the kth column
has a value 1 in the ith row, -1 in the jth row
and 0 elsewhere.
• For example, the Incidence matrix for the
graph of figure is:
• We observe that, e1 = (v1, v2), e2 = (v2, v4), e3 =
(v4, v3 ), e4 = (v3, v5), e5 = (v5, v1 ), e6 = (v1, v3 )
and e7 = (v5, v4 ) .
• So , 1st edge (e1 ) has vertices v1 and v2 and
hence the first column has the value 1 in the
1st row , -1 in the 2nd row. Similarly 3rd edge (e3
) has vertices v4 and v3 and hence the third
column has the value 1 in the 4th row , -1 in
the 3rd row. We see that zero is elsewhere.
• If the vertex is having a self-loop, in such case
the kth edge is (vi, vi ), then this will be
represented in a matrix with 1.