B.

Sc Part-I Paper-B Section (B)

Data Structure

 Graphs:

A graph is non linear and dynamic data structure that represents data in many to many relationship forms. A
Graph is made up of set of nodes and lines. Nodes are called vertices which hold the data while lines are called
edges or arcs. Lines are used to connect the nodes. An edge of a graph can be represented by:

e = [u, v]
‘u’ denotes the start of node and ‘v’ represents end of the node; while ‘e’ represents the edge.
e
u v
Edge Vertex / node

Graphs are important because these are used to represents many to many relationship. Thus graphs are used to
study problem in a wide variety of areas.

Daily life example of graph:

A graph of airplane flights to different cities:-

Quetta Peshawar

Islamabad

Karachi Lahore

Basic Terminologies of Graphs:

 Degree of a node /vertex:
The number of edges that a node contains is called its degree.

A B

C D

In above graph the degree of A= 2, B= 3, C= 3 and D= 2

Chapter# 7 | Graphs 1
  Out-degree and In-degree of node:
The number of edges beginning from a node is called the out-degree of the node. Similarly the number
of edges ending at node is called in-degree of the node.

A B

E
C D
In above graph:
In-degree of node A= 0; Out-degree of node A= 2 In-degree of node B= 1; Out-degree of node B= 2
In-degree of node C= 2; Out-degree of node C= 0 In-degree of node D= 2; Out-degree of node D= 1
In-degree of node E= 1; Out-degree of node E= 1
 Source node and Sink node:
A node that has positive out-degree but zero in-degree is called source node. Similarly a node that has
positive in degree but zero out-degree is called sink node.

A B

E
C D

In above graph, node A is the source node as it has positive out degree and zero in-degree. Similarly node E is
sink node because it has positive in-degree and zero out-degree.

 Pendent node:
A node is said to be pendent node if it has total degree of one. Pendent node has total one in-degree or
one out degree.
A B A B

C D C D

Node ‘A’ is pendent node. Node ‘B’ is pendent node

 Loop edge:
An edge is said to be a loop edge if it has the same starting and ending node.

A B

In node ‘B’ there is a loop edge.

Chapter# 7 | Graphs 2
  Path of graph:
A list of nodes of graph where each node has an edge from it to the next node is called the path. It is
written as a sequence of nodes u1, u2, u3 …
A path which repeats no nodes is known as simple path.
While a path which repeats a node is called cyclic path.

A B A B

C D C D

Simple path: A, C, D, B Cyclic Path: A, B, C, A

 Multiple edges:
The edges that have the same starting and ending point are called multiple or parallel edges.

A C
Multiple edges

Types of Graph
Graph has following different types:

 Undirected Graph:
A graph whose edges don’t have any direction is called undirected graph. It is also called an undigraph.
A line segment is used as an edge.
Example:

A B

C D

 Directed Graph:
A graph whose edges have a direction is called directed graph. It is also called digraph. The arrow sign
is used as an edge.
Example:
A B

C D

Chapter# 7 | Graphs 3
 Weight graph:
A graph which has a weight or number, associated with each edge is called weight graph; weight of an
edge is sometimes also called its cost.
A weight graph denotes the magnitude between nodes.
Example:

7
A B

3 4

C D
8

 Complete Graph:
A graph is said to be complete if its every node is connected to every other node. In complete graph
there is an edge between every node. A complete graph with ‘n’ nodes have ‘n (n-1)/2’ nodes.
Example:

A B

C D

 Tree Graph:
A graph is said to be tree graph if there is a unique simple path between any two nodes. A tree graph
doesn’t have any cycle path.
Example:
A B

C C D

 Regular Graph:
A graph is said to be regular graph if each node has total equal in-degree and out-degree. In regular
graph the degree of all nodes is equal.
Example: A B

C C

In this graph each node has 2 in and out degree. So it is a regular graph.

Chapter# 7 | Graphs 4
  Cyclic Graph:
A directed graph which has a cycle is called cyclic graph. In cyclic graph there must be at least one
cyclic path.
Example:
A C

 Acyclic Graph:
A directed graph that has no cycle is called acyclic graph. In an acyclic graph there will be no cyclic
path. It is also called Directed Acyclic Graph (DAG).
Example:
A C

 Representation of Graphs in Compute Memory:

There are two different methods to represent graph in computer memory. They are:

 Adjacency Matrix
 Adjacency List

Now we will describe each of the above one by one here below:

 Adjacency Matrix:
Adjacency matrix is a table, which represents the edges between nodes of graph. In this method a matrix
is used to represent graph. The presence of edge between nodes is represented by 1 while the absence of
node between nodes is represented by 0. The column of the matrix represents the starting of the edge
and row of the matrix represent the end of the edge.
If there are ‘N’ nodes then the adjacency matrix will be ‘N x N’ matrix.

The adjacency matrix of graph shown below is:

A B C D E

A B A 0 1 1 0 0
B 0 0 0 1 1
E
C 0 0 0 1 0
C D
D 0 0 0 0 1
E 0 0 0 0 1

Chapter# 7 | Graphs 5
 Adjacency List:
In this method the graph is represented by link list. In adjacency method the nodes are stored in an array.
And all the nodes which are connected to a node are represented in form of link list, which is attached to
that node.
For example let we have the following graph:

A B

C D

The adjacency list of the above graph is:

A B  C
Nodes List of
Connected
nodes B A  C  D
A B, C
B A, C, D
C A, B, D C A  B  D
D B, C

D B  C

 
Prepared By: Muhammad Fayaz
M.Sc Computer Science, SBBU.
Contact#: 0342-5850786
E-mail: [email protected]

‫م ز ہ  د‬ ‫د  ا‬
‫ہ  د‬  ‫ن‬

Chapter# 7 | Graphs 6