Asst. Prof.

Praveen Sebastian Paul, Don Bosco College, Kottiyam

MODULE 4
GRAPH

A graph data structure is a collection of nodes that have data and are
connected to other nodes.
A graph is a pictorial representation of a set of objects where some pairs
of objects are connected by links. The interconnected objects are represented by
points termed as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices
and E is the set of edges, connecting the pairs of vertices. Take a look at the
following graph −

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Directed and Undirected Graph

A graph can be directed or undirected. However, in an undirected graph,
edges are not associated with the directions with them. If an edge exists between
vertex A and B then the vertices can be traversed from B to A as well as A to B.
In a directed graph, edges form an ordered pair. Edges represent a specific
path from some vertex A to another vertex B. Node A is called initial node while
node B is called terminal node.

Mathematical graphs can be represented in data structure. We can

represent a graph using an array of vertices and a two-dimensional array of edges.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

Before we proceed further, let's familiarize ourselves with some important terms
−
• Vertex − Each node of the graph is represented as a vertex. Generally, a
labelled circle represents vertices.

• Edge − Edge represents a path between two vertices or a line between two
vertices.

• Adjacency − Two node or vertices are adjacent if they are connected to

each other through an edge.

• Path - A path can be defined as the sequence of vertices that are followed
in order to reach some terminal node V from the initial node U.

• Closed Path - A path will be called as closed path if the initial node is
same as terminal node. A path will be closed path if V0=VN.

• Simple Path - If all the nodes of the graph are distinct with an exception
V0=VN, then such path P is called as closed simple path.

• Cycle - A cycle can be defined as the path which has no repeated edges or
vertices except the first and last vertices.

• Loop - An edge that is associated with the similar end points can be called
as Loop.

• Degree of the Node - A degree of a node is the number of edges that are
connected with that node. A node with degree 0 is called as isolated node.

• Connected Graph - A connected graph is the one in which some path

exists between every two vertices (u, v) in V. There are no isolated nodes
in connected graph.

• Complete Graph - A complete graph is the one in which every node is

connected with all other nodes. A complete graph contain n(n-1)/2 edges
where n is the number of nodes in the graph.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

• Weighted Graph - In a weighted graph, each edge is assigned with some

data such as length or weight. The weight of an edge e can be given as
w(e) which must be a positive (+) value indicating the cost of traversing
the edge.

• Digraph - A digraph is a directed graph in which each edge of the graph

is associated with some direction and the traversing can be done only in
the specified direction.

Following are basic primary operations of a Graph −

• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.

Graph Representations
In graph theory, a graph representation is a technique to store graph into
the memory of computer.
To represent a graph, we just need the set of vertices, and for each vertex
the neighbors of the vertex (vertices which is directly connected to it by an edge).
If it is a weighted graph, then the weight will be associated with each edge.
There are different ways to optimally represent a graph, depending on the
density of its edges, type of operations to be performed and ease of use.

1. Adjacency Matrix
• Adjacency matrix is a sequential representation.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

• It is used to represent which nodes are adjacent to each other. i.e. is there
any edge connecting nodes to a graph.
• In this representation, we have to construct a nXn matrix A. If there is any
edge from a vertex i to vertex j, then the corresponding element of A, ai,j =
1, otherwise ai,j= 0.
• If there is any weighted graph then instead of 1s and 0s, we can store the
weight of the edge.

Note, even if the graph on 100 vertices contains only 1 edge, we still have to have
a 100x100 matrix with lots of zeroes.

Example

Undirected graph representation

Directed graph represenation

2. Incidence Matrix

In Incidence matrix representation, graph can be represented using a

matrix of size:

Total number of vertices by total number of edges. It means if a graph has 4

vertices and 6 edges, then it can be represented using a matrix of 4X6 class. In
this matrix, columns represent edges and rows represent vertices.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

This matrix is filled with either 0 or 1 or -1. Where,

• 0 is used to represent row edge which is not connected to column vertex.

• 1 is used to represent row edge which is connected as outgoing edge to
column vertex.
• -1 is used to represent row edge which is connected as incoming edge to
column vertex.

Example

Consider the following directed graph representation.

3. Adjacency List
• Adjacency list is a linked representation.
• In this representation, for each vertex in the graph, we maintain the list of
its neighbors. It means, every vertex of the graph contains list of its
adjacent vertices.
• We have an array of vertices which is indexed by the vertex number and
for each vertex v, the corresponding array element points to a singly linked
list of neighbors of v.

Example

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

SHORT QUESTIONS

1. Define graph with an example.

Graph is a collection of nodes and edges which connects nodes in the graph
Generally, a graph G is represented as G = ( V , E ), where V is set of
vertices and E is set of edges.
Example
The following is a graph with 5 vertices and 6 edges.
This graph G can be defined as G = ( V , E )
Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

2. Define Vertex of a graph.

An individual data element of a graph is called as Vertex. Vertex is also
known as node. In above example graph, A, B, C, D & E are known as vertices.

3. Define Edge of a graph. What are its types?

An edge is a connecting link between two vertices. Edge is also known
as Arc. An edge is represented as (startingVertex, endingVertex). For example,
in above graph, the link between vertices A and B is represented as (A,B). In
above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E),
(C,D), (D,E)).
Edges are three types.
1. Undirected Edge - An undirected egde is a bidirectional edge. If there is
a undirected edge between vertices A and B then edge (A,B) is equal to edge
(B,A).
2. Directed Edge - A directed egde is a unidirectional edge. If there is a
directed edge between vertices A and B then edge (A , B) is not equal to edge
(B , A).
3. Weighted Edge - A weighted egde is an edge with cost on it.

4. Define Undirected Graph

A graph with only undirected edges is said to be undirected graph.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

5. Define Directed Graph

A graph with only directed edges is said to be directed graph.

6. Define Mixed Graph

A graph with undirected and directed edges is said to be mixed graph.

7. What do you meant by End vertices or Endpoints?

The two vertices joined by an edge are called the end vertices (or
endpoints) of the edge.

8. What do you meant by Origin and Destination?

If an edge is directed, its first endpoint is said to be origin of it and the
other endpoint is said to be the destination of the edge.

9. When we can say two vertices are Adjacent?

If there is an edge between vertices A and B then both A and B are said to
be adjacent. In other words, Two vertices A and B are said to be adjacent if there
is an edge whose end vertices are A and B.

10. Define Degree of a graph.

Total number of edges connected to a vertex is said to be degree of that
vertex.

11. Define In-degree of a graph.

Total number of incoming edges connected to a vertex is said to be in
degree of that vertex.

12. Define Out-degree of a graph.

Total number of outgoing edges connected to a vertex is said to be out
degree of that vertex.

13. What do you meant by Parallel edges or Multiple edges?

If there are two undirected edges to have the same end vertices, and for
two directed edges to have the same origin and the same destination. Such edges
are called parallel edges or multiple edges.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

14. What do you meant by Self-loop of a graph?

An edge (undirected or directed) is a self-loop if its starting node and
ending node is same.

15. What is a Simple Graph?

A graph is said to be simple if there are no parallel and self-loop edges.

16. Define Path of a graph.

A path is a sequence of alternating vertices and edges that starts at a vertex
and ends at a vertex such that each edge is incident to its predecessor and
successor vertex.

17. What do you meant by Back tracking?

Back tracking is coming back to the vertex from which we came to
current vertex.

18. What are the uses of graphs?

They can be used to model many types of relations and process dynamics
in computer science, physical, biological and social systems. They can be
used to model pair wise relations between objects from a certain collection.
Some of its applications are
• Transportation networks: Highway network, Flight network.
• Computer networks: Local area network, Internet, Web.
• Representing relationships between components in electronic circuits.
• Databases: For representing ER(Entity Relationship) diagrams in databases,
for representing dependency of tables in databases.
• Connecting with friends on social media, where each user is a vertex, and
when users connect they create an edge.
• Using GPS/Google Maps/Yahoo Maps, to find a route based on shortest
route.
• Google, to search for webpages, where pages on the internet are linked to
each other by hyperlinks; each page is a vertex and the link between two
pages is an edge.
• On eCommerce websites relationship graphs are used to show
recommendations.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

LONG QUESTIONS

1. what is a graph?
A graph is a pictorial representation of a set of objects where some pairs of
objects are connected by links. The interconnected objects are represented by
points termed as vertices, and the links that connect the vertices are called edges.
Formally, a graph is a pair of sets (V, E), where V is the set of vertices
and E is the set of edges, connecting the pairs of vertices. Take a look at the
following graph −

In the above graph,

V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}

Graph Data Structure

Mathematical graphs can be represented in data structure. We can represent
a graph using an array of vertices and a two-dimensional array of edges. Before
we proceed further, let's familiarize ourselves with some important terms −

Vertex − Each node of the graph is represented as a vertex. In the following

example, the labeled circle represents vertices. Thus, A to G are vertices. We can
represent them using an array as shown in the following image. Here A can be
identified by index 0. B can be identified using index 1 and so on.
Edge − Edge represents a path between two vertices or a line between two
vertices. In the following example, the lines from A to B, B to C, and so on
represents edges. We can use a two-dimensional array to represent an array as
shown in the following image. Here AB can be represented as 1 at row 0, column
1, BC as 1 at row 1, column 2 and so on, keeping other combinations as 0.
Adjacency − Two node or vertices are adjacent if they are connected to each
other through an edge. In the following example, B is adjacent to A, C is adjacent
to B, and so on.
Path − Path represents a sequence of edges between the two vertices. In the
following example, ABCD represents a path from A to D.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

Basic Operations
Following are basic primary operations of a Graph −
• Add Vertex − Adds a vertex to the graph.
• Add Edge − Adds an edge between the two vertices of the graph.
• Display Vertex − Displays a vertex of the graph.

2. Write notes on Depth First Search (DFS)

Depth First Search (DFS) algorithm traverses a graph in a depthward
motion and uses a stack to remember to get the next vertex to start a search, when
a dead end occurs in any iteration.
DFS traversal of a graph, produces a spanning tree as final
result. Spanning Tree is a graph without any loops. We use Stack data
structure with maximum size of total number of vertices in the graph to
implement DFS traversal of a graph.

As in the example given above, DFS algorithm traverses from A to B to C to D

first then to E, then to F and lastly to G. It employs the following rules.
• Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it.
Push it in a stack.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

• Rule 2 − If no adjacent vertex is found, pop up a vertex from the stack. (It
will pop up all the vertices from the stack, which do not have adjacent
vertices.)
• Rule 3 − Repeat Rule 1 and Rule 2 until the stack is empty.

We use the following steps to implement DFS traversal

Step 1: Define a Stack of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and
push it on to the Stack.
Step 3: Visit any one of the adjacent vertex of the vertex which is at top of the
stack which is not visited and push it on to the stack.
Step 4: Repeat step 3 until there are no new vertex to be visit from the vertex
on top of the stack.
Step 5: When there is no new vertex to be visit then use back tracking and pop
one vertex from the stack.
Step 6: Repeat steps 3, 4 and 5 until stack becomes Empty.
Step 7: When stack becomes Empty, then produce final spanning tree by
removing unused edges from the graph

Back tracking is coming back to the vertex from which we came to current
vertex.

Step Traversal Description OUTPUT

Initialize the stack.

1.

Mark S as visited and put it S

onto the stack. Explore any
unvisited adjacent node
from S. We have three
2.
nodes and we can pick any
of them. For this example,
we shall take the node in an
alphabetical order.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

Mark A as visited and put it SA

onto the stack. Explore any
unvisited adjacent node
3. from A. Both S and D are
adjacent to A but we are
concerned for unvisited
nodes only.
Visit D and mark it as SAD
visited and put onto the
stack. Here, we
have B and C nodes, which
4.
are adjacent to D and both
are unvisited. However, we
shall again choose in an
alphabetical order.
We choose B, mark it as SADB
visited and put onto the
stack. Here B does not have
5.
any unvisited adjacent node.
So, we pop B from the
stack.
We check the stack top for SADB
return to the previous node
and check if it has any
6.
unvisited nodes. Here, we
find D to be on the top of the
stack.
Only unvisited adjacent SADBC
node is from D is C now. So
7. we visit C, mark it as visited
and put it onto the stack.

As C does not have any unvisited adjacent node so we keep popping the
stack until we find a node that has an unvisited adjacent node. In this case, there's
none and we keep popping until the stack is empty.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

3. Write notes on Breadth First Search (BFS)

Breadth First Search (BFS) algorithm traverses a graph in a breadthward
motion and uses a queue to remember to get the next vertex to start a search,
when a dead end occurs in any iteration.

BFS traversal of a graph produces a spanning tree as final

result. Spanning Tree is a graph without any loops. We use Queue data
structure with maximum size of total number of vertices in the graph to
implement BFS traversal of a graph.

As in the example given above, BFS algorithm traverses from A to B to E

to F first then to C and G lastly to D. It employs the following rules.

• Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it.
Insert it in a queue.
• Rule 2 − If no adjacent vertex is found, remove the first vertex from the
queue.
• Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

We use the following steps to implement BFS traversal

Step 1: Define a Queue of size total number of vertices in the graph.

Step 2: Select any vertex as starting point for traversal. Visit that vertex and
insert it into the Queue.

Step 3: Visit all the adjacent vertices of the vertex which is at front of the
Queue which is not visited and insert them into the Queue.

Step 4: When there is no new vertex to be visit from the vertex at front of the
Queue then delete that vertex from the Queue.

Step 5: Repeat step 3 and 4 until queue becomes empty.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

Step 6: When queue becomes Empty, then produce final spanning tree by
removing unused edges from the graph

Step Traversal Description OUTPUT

Initialize the queue.
1.

We start from visiting S (starting S

2. node), and mark it as visited.

We then see an unvisited adjacent S A

node from S. In this example, we
3. have three nodes but
alphabetically we choose A,
mark it as visited and enqueue it.
Next, the unvisited adjacent node S A B
from S is B. We mark it as visited
4.
and enqueue it.

Next, the unvisited adjacent node S A B C

from S is C. We mark it as visited
5.
and enqueue it.

Now, S is left with no unvisited S A B C

adjacent nodes. So, we dequeue
6. and find A.

From A we have D as unvisited S A B C D

adjacent node. We mark it as
7.
visited and enqueue it.

At this stage, we are left with no unmarked (unvisited) nodes. But as per
the algorithm we keep on dequeuing in order to get all unvisited nodes. When the
queue gets emptied, the program is over.

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

4. What are the applications of a graph?

Since they are powerful abstractions, graphs can be very important in

modelling data. In fact, many problems can be reduced to known graph problems.
They can be used to model many types of relations and process dynamics in
computer science, physical, biological and social systems. They can be used to
model pair wise relations between objects from a certain collection.

Here we outline just some of the many applications of graphs.

1. Social network graphs: to tweet or not to tweet. Graphs that represent who
knows whom, who communicates with whom, who influences whom or other
relationships in social structures. An example is the twitter graph of who follows
whom. These can be used to determine how information flows, how topics
become hot, how communities develop, or even who might be a good match for
who, or is that whom.

2. Transportation networks. In road networks vertices are intersections and

edges are the road segments between them, and for public transportation
networks vertices are stops and edges are the links between them. Such networks
are used by many map programs such as Google maps, Bing maps and now Apple
IOS 6 maps (well perhaps without the public transport) to find the best routes
between locations. They are also used for studying traffic patterns, traffic light
timings, and many aspects of transportation.

3. Utility graphs. The power grid, the Internet, and the water network are all
examples of graphs where vertices represent connection points, and edges the
wires or pipes between them. Analyzing properties of these graphs is very
important in understanding the reliability of such utilities under failure or attack,
or in minimizing the costs to build infrastructure that matches required demands.

4. Document link graphs. The best known example is the link graph of the web,
where each web page is a vertex, and each hyperlink a directed edge. Link graphs
are used, for example, to analyze relevance of web pages, the best sources of
information, and good link sites.

5. Protein-protein interactions graphs. Vertices represent proteins and edges

represent interactions between them that carry out some biological function in
the cell. These graphs can be used, for example, to study molecular pathways—

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

chains of molecular interactions in a cellular process. Humans have over 120K

proteins with millions of interactions among them.

6. Network packet traffic graphs. Vertices are IP (Internet protocol) addresses

and edges are the packets that flow between them. Such graphs are used for
analyzing network security, studying the spread of worms, and tracking criminal
or non-criminal activity.

7. Scene graphs. In graphics and computer games scene graphs represent the
logical or spacial relationships between objects in a scene. Such graphs are very
important in the computer games industry.

8. Finite element meshes. In engineering many simulations of physical systems,

such as the flow of air over a car or airplane wing, the spread of earthquakes
through the ground, or the structural vibrations of a building, involve partitioning
space into discrete elements. The elements along with the connections between
adjacent elements forms a graph that is called a finite element mesh.

9. Robot planning. Vertices represent states the robot can be in and the edges
the possible transitions between the states. This requires approximating
continuous motion as a sequence of discrete steps. Such graph plans are used, for
example, in planning paths for autonomous vehicles.

10. Neural networks. Vertices represent neurons and edges the synapses
between them. Neural networks are used to understand how our brain works and
how connections change when we learn. The human brain has about 1011 neurons
and close to 1015 synapses.

11. Graphs in quantum field theory. Vertices represent states of a quantum

system and the edges the transitions between them. The graphs can be used to
analyze path integrals and summing these up generates a quantum amplitude
(yes, I have no idea what that means).

12. Semantic networks. Vertices represent words or concepts and edges

represent the relationships among the words or concepts. These have been used
in various models of how humans organize their knowledge, and how machines
might simulate such an organization.

13. Graphs in epidemiology. Vertices represent individuals and directed edges

the transfer of an infectious disease from one individual to another. Analyzing

[email protected]
Asst. Prof. Praveen Sebastian Paul, Don Bosco College, Kottiyam

such graphs has become an important component in understanding and

controlling the spread of diseases.

14. Graphs in compilers. Graphs are used extensively in compilers. They can
be used for type inference, for so called data flow analysis, register allocation
and many other purposes. They are also used in specialized compilers, such as
query optimization in database languages.

15. Constraint graphs. Graphs are often used to represent constraints among
items. For example the GSM network for cell phones consists of a collection of
overlapping cells. Any pair of cells that overlap must operate at different
frequencies. These constraints can be modeled as a graph where the cells are
vertices and edges are placed between cells that overlap.

16. Dependence graphs. Graphs can be used to represent dependences or

precedences among items. Such graphs are often used in large projects in laying
out what components rely on other components and used to minimize the total
time or cost to completion while abiding by the dependences.

[email protected]