Data Structure of computer science and technology

UNIT-5
NON-LINEAR DATA STRUCTURES-
GRAPHS
Graph, Graph terminology, Graph
Traversals- Breadth First Traversals, Depth
first traversals, minimal spanning trees

Introduction:
• A graph is an abstract data structure that is used to implement the mathematical concept of graphs.
• It is basically a collection of vertices (also called nodes) and edges that connect these vertices.
• A graph is often viewed as a generalization of the tree structure, where instead of having a purely parent-to-
child relationship between tree nodes, any kind of complex relationship can exist.
Why are Graphs Useful?
Graphs are widely used to model any situation where entities or things are related to each other in pairs.
Example:
• Family trees in which the member nodes have an edge from parent to each of their children.
• Transportation networks in which nodes are airports, intersections, ports, etc. The edges can be airline flights,
one-way roads, shipping routes, etc.

Definition
A graph G is defined as an ordered set (V, E), where V(G) represents the set of vertices and E(G) represents
the edges that connect these vertices.
The figure shows a graph with V(G) = {A, B, C, D and E} and E(G) = {(A, B), (B, C), (A, D), (B, D), (D,
E), (C, E)}.
Undirected graph
Directed graph
In an undirected graph, edges do not have any direction
associated with them. That is, if an edge is drawn between
nodes A and B, then the nodes can be traversed from A to B as
well as from B to A.
In a directed graph, edges form an ordered pair. If there is an
edge from A to B, then there is a path from A to B but not from
B to A. The edge (A, B) is said to initiate from node A (also
known as initial node) and terminate at node B (terminal node).

Vertex
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.
Edge
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 6 edges (i.e., (A,B), (A,D), (B,D), (B,C), (C,E), (D,E)).
Edges are three types.
1.Undirected Edge - An undirected egde is a bidirectional edge. If there is 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 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 a edge with value (cost) on it.

Graph Terminology
• Adjacent nodes or neighbours For every edge, e = (u, v) that connects nodes u and v, the nodes u and
v are the end-points and are said to be the adjacent nodes or neighbours.
• Degree of a node Degree of a node u, deg(u), is the total number of edges containing the node u. If
deg(u) = 0, it means that u does not belong to any edge and such a node is known as an isolated node.
• Regular graph It is a graph where each vertex has the same number of neighbours. That is, every node
has the same degree. A regular graph with vertices of degree k is called a k–regular graph or a regular
graph of degree k.

• Path A path P written as P = {v0 , v1 , v2 , ..., vn ), of length n from a node u to v is defined as a sequence of (n+1)
nodes. Here, u = v0 , v = vn and vi–1 is adjacent to vi for i = 1, 2, 3, ..., n.
• Closed path A path P is known as a closed path if the edge has the same end-points. That is, if v0 = vn.
• Simple path A path P is known as a simple path if all the nodes in the path are distinct with an exception that v0 may
be equal to vn . If v0 = vn , then the path is called a closed simple path.
• Cycle A path in which the first and the last vertices are same. A simple cycle has no repeated edges or vertices
(except the first and last vertices).
• Connected graph A graph is said to be connected if for any two vertices (u, v) in V there is a path from u to v. That
is to say that there are no isolated nodes in a connected graph. A connected graph that does not have any cycle is
called a tree. Therefore, a tree is treated as a special graph

Complete graph A graph G is said to be complete if all its nodes are fully connected. That is, there is a path from
one node to every other node in the graph. A complete graph has n(n–1)/2 edges, where n is the number of nodes
in G.
Labelled graph or weighted graph A graph is said to be labelled if every edge in the graph is assigned some
data. In a weighted graph, the edges of the graph are assigned some weight or length. The weight of an edge
denoted by w(e) is a positive value which indicates the cost of traversing the edge.
Multiple edges Distinct edges which connect the same end-points are called multiple edges. That is, e = (u, v)
and e' = (u, v) are known as multiple edges of G.
Loop An edge that has identical end-points is called a loop. That is, e = (u, u).
Multi-graph A graph with multiple edges and/or loops is called a multi-graph.
Size of a graph The size of a graph is the total number of edges in it.

Directed Graphs
A directed graph G, also known as a digraph, is a graph in which every edge has a direction
assigned to it.
An edge of a directed graph is given as an ordered pair (u, v) of nodes in G. For an edge (u, v),
• The edge begins at u and terminates at v.
• u is known as the origin or initial point of e. Correspondingly, v is known as the destination or
terminal point of e.
• u is the predecessor of v. Correspondingly, v is the successor of u.
• Nodes u and v are adjacent to each other.

Graph data structure is represented using following representations...
1.Adjacency Matrix
2.Incidence Matrix
3.Adjacency List
Adjacency Matrix
In this representation, the graph is represented using a matrix of size total number of vertices by a total number of
vertices. That means a graph with 4 vertices is represented using a matrix of size 4X4. In this matrix, both rows
and columns represent vertices. This matrix is filled with either 1 or 0. Here, 1 represents that there is an edge from
row vertex to column vertex and 0 represents that there is no edge from row vertex to column vertex.
For example, consider the following undirected graph representation...
GRAPH REPRESENTATIONS

Data Structure of computer science and technology

Incidence Matrix
In this representation, the graph is represented using a matrix of size total number of vertices by a total number of
edges. That means graph with 4 vertices and 6 edges is represented using a matrix of size 4X6. In this matrix, rows
represent vertices and columns represents edges. This matrix is filled with 0 or 1 or -1. Here, 0 represents that the row
edge is not connected to column vertex, 1 represents that the row edge is connected as the outgoing edge to column
vertex and -1 represents that the row edge is connected as the incoming edge to column vertex.
For example, consider the following directed graph representation...

Adjacency List
In this representation, every vertex of a graph contains list of its adjacent vertices.
For example, consider the following directed graph representation implemented using linked list...
This representation can also be implemented using an
array as follows..

GRAPH TRAVERSAL ALGORITHMS
By traversing a graph, we mean the method of examining the nodes and edges of the graph. There are two
standard methods of graph traversal. These two methods are:
1. Breadth-first search
2. Depth-first search
While breadth-first search uses a queue as an auxiliary data structure to store nodes for further processing,
the depth-first search scheme uses a stack.
But both these algorithms make use of a variable STATUS. During the execution of the algorithm, every
node in the graph will have the variable STATUS set to 1 or 2, depending on its current state.
Status State of the node Description
1 Ready The initial state of the node N
2 Waiting Node N is placed on the queue or stack and waiting
to be processed
3 Processed Node N has been completely processed

Breadth-First Search Algorithm
• Breadth-first search (BFS) is a graph search algorithm that begins at the root node and explores all the
neighbouring nodes.
• Then for each of those nearest nodes, the algorithm explores their unexplored neighbour nodes, and so on,
until it finds the goal.
• That is, we start examining the node A and then all the neighbours of A are examined. In the next step, we
examine the neighbours of neighbours of A, so on and so forth. This means that we need to track the
neighbours of the node and guarantee that every node in the graph is processed and no node is processed
more than once.
• This is accomplished by using a queue that will hold the nodes that are waiting for further processing and a
variable STATUS to represent the current state of the node.

Consider the graph G given in Fig. The adjacency list of G is also given. Assume that Graph represents the
daily flights between different cities and we want to fly from city A to I with minimum stops. That is, find the
minimum path P from A to I given that every edge has a length of 1.
The minimum path P can be found by applying the
breadth-first search algorithm that begins at city A and
ends when I is encountered. During the execution of the
algorithm, we use two arrays: QUEUE and ORIG. While
QUEUE is used to hold the nodes that have to be
processed, ORIG is used to keep track of the origin of
each edge. Initially, FRONT = REAR = –1. The
algorithm for this is as follows:
(a) Add A to QUEUE and add NULL to ORIG

(b) Dequeue a node by setting FRONT = FRONT + 1 (remove the FRONT element of QUEUE) and enqueue the
neighbours of A. Also, add A as the ORIG of its neighbours.
(c) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of B. Also, add B as the ORIG of
its neighbours.
(d) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of C. Also, add C as the ORIG of
its neighbours. Note that C has two neighbours B and G. Since B has already been added to the queue and it is not in
the Ready state, we will not add B and only add G.

(e) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of D. Also, add D as the ORIG of its
neighbours. Note that D has two neighbours C and G. Since both of them have already been added to the queue and
they are not in the Ready state, we will not add them again.
(f) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of E. Also, add E as the ORIG of its
neighbours. Note that E has two neighbours C and F. Since C has already been added to the queue and it is not in the
Ready state, we will not add C and add only F.
(g) Dequeue a node by setting FRONT = FRONT + 1 and enqueue the neighbours of G. Also, add G as the ORIG of its
neighbours. Note that G has three neighbours F, H, and I.
Since F has already been added to the queue, we will only add H and I. As I is our final destination, we stop the
execution of this algorithm as soon as it is encountered and added to the QUEUE. Now, backtrack from I using ORIG to
find the minimum path P. Thus, we have P as A -> C -> G -> I.

•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 non-
visited adjacent vertices of the vertex which is at
front of the Queue and insert them into the Queue.
•Step 4 - When there is no new vertex to be
visited from the vertex which is at front of the
Queue then delete that vertex.
•Step 5 - Repeat steps 3 and 4 until queue
becomes empty.
•Step 6 - When queue becomes empty, then
produce final spanning tree by removing unused
edges from the graph

Applications of Breadth-First Search Algorithm
Breadth-first search can be used to solve many problems such as:
• Finding all connected components in a graph G.
• Finding all nodes within an individual connected component.
• Finding the shortest path between two nodes, u and v, of an unweighted graph.
• Finding the shortest path between two nodes, u and v, of a weighted graph.

Depth-first Search Algorithm
• The depth-first search algorithm progresses by expanding the starting node of G and then going deeper and deeper
until the goal node is found, or until a node that has no children is encountered.
• When a dead-end is reached, the algorithm backtracks, returning to the most recent node that has not been
completely explored.
• In other words, depth-first search begins at a starting node A which becomes the current node. Then, it examines
each node N along a path P which begins at A. That is, we process a neighbour of A, then a neighbour of
neighbour of A, and so on.
• During the execution of the algorithm, if we reach a path that has a node N that has already been processed, then
we backtrack to the current node. Otherwise, the unvisited (unprocessed) node becomes the current node.
• The algorithm proceeds like this until we reach a dead-end (end of path P). On reaching the deadend, we backtrack
to find another path P’. The algorithm terminates when backtracking leads back to the starting node A. In this
algorithm, edges that lead to a new vertex are called discovery edges and edges that lead to an already visited
vertex are called back edges

Consider the graph G given in Fig. The adjacency list of G is also given. Suppose we want to print all the nodes that
can be reached from the node H (including H itself). One alternative is to use a depth-first search of G starting at
node H. The procedure can be explained here
(a) Push H onto the stack
(b) Pop and print the top element of the STACK, that is, H. Push all
the neighbours of H onto the stack that are in the ready state. The
STACK now becomes
(c) Pop and print the top element of the STACK, that is, I. Push all
the neighbours of I onto the stack that are in the ready state. The
STACK now becomes
(d) Pop and print the top element of the STACK, that is, F. Push all the neighbours of F onto the stack that are in
the ready state. (Note F has two neighbours, C and H. But only C will be added, as H is not in the ready state.)
The STACK now becomes

(e) Pop and print the top element of the STACK, that is, C. Push all the neighbours of C onto the stack that are in the
ready state. The STACK now becomes
(f) Pop and print the top element of the STACK, that is, G. Push all the neighbours of G onto the stack that are in
the ready state. Since there are no neighbours of G that are in the ready state, no push operation is performed. The
STACK now becomes
(g) Pop and print the top element of the STACK, that is, B. Push all the neighbours of B onto the stack that are in the
ready state. Since there are no neighbours of B that are in the ready state, no push operation is performed. The
STACK now becomes
(h) Pop and print the top element of the STACK, that is, E. Push all the neighbours of E onto the stack that are in the
ready state. Since there are no neighbours of E that are in the ready state, no push operation is performed. The STACK
now becomes empty.
Since the STACK is now empty, the depth-first search of G starting at node H is complete and the nodes which were
printed are: H, I, F, C, G, B, E These are the nodes which are reachable from the node H.

•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 non-
visited adjacent vertices of a vertex which is at the top of
stack and push it on to the stack.
•Step 4 - Repeat step 3 until there is no new vertex to be
visited from the vertex which is at the top of the stack.
•Step 5 - When there is no new vertex to 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

Applications of Depth-First Search Algorithm
• Finding a path between two specified nodes, u and v, of an unweighted graph.
• Finding a path between two specified nodes, u and v, of a weighted graph.
• Finding whether a graph is connected or not.
• Computing the spanning tree of a connected graph.

Minimum Spanning Trees
• A spanning tree of a connected, undirected graph G is a sub-graph of G which is a tree that connects all the
vertices together.
• A graph G can have many different spanning trees. We can assign weights to each edge (which is a number
that represents how unfavourable the edge is), and use it to assign a weight to a spanning tree by calculating
the sum of the weights of the edges in that spanning tree.
• A minimum spanning tree (MST) is defined as a spanning tree with weight less than or equal to the weight of
every other spanning tree. In other words, a minimum spanning tree is a spanning tree that has weights
associated with its edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum.
• Many distinct spanning trees can be obtained from this graph, but a minimum spanning tree would be the one
with the lowest total cost.

Properties:
Possible multiplicity :There can be multiple minimum spanning trees of the same weight. Particularly, if all the
weights are the same, then every spanning tree will be minimum.
Uniqueness: When each edge in the graph is assigned a different weight, then there will be only one unique
minimum spanning tree.
Minimum-cost subgraph: If the edges of a graph are assigned non-negative weights, then a minimum spanning
tree is in fact the minimum-cost subgraph or a tree that connects all vertices.
Cycle property If there exists a cycle C in the graph G that has a weight larger than that of other edges of C, then
this edge cannot belong to an MST.
Usefulness Minimum spanning trees can be computed quickly and easily to provide optimal solutions. These trees
create a sparse subgraph that reflects a lot about the original graph.
Simplicity The minimum spanning tree of a weighted graph is nothing but a spanning tree of the graph which
comprises of n–1 edges of minimum total weight. Note that for an unweighted graph, any spanning tree is a
minimum spanning tree.

Consider an unweighted graph G given below. From G, draw distinct spanning trees
Unweighted graph and its spanning trees

Consider a weighted graph G shown in Fig.. From G, draw distinct spanning trees. Obtain a single minimum spanning
tree can be obtained, that is, the one that has the minimum weight (cost) associated with it.
Weighted graph and its spanning trees

Applications of Minimum Spanning Trees
1. MSTs are widely used for designing networks. For instance, people separated by varying distances wish
to be connected together through a telephone network. A minimum spanning tree is used to determine the
least costly paths with no cycles in this network, thereby providing a connection that has the minimum cost
involved.
2. MSTs are used to find airline routes. While the vertices in the graph denote cities, edges represent the
routes between these cities. No doubt, more the distance between the cities, higher will be the amount
charged. Therefore, MSTs are used to optimize airline routes by finding the least costly path with no
cycles.
3. MSTs are also used to find the cheapest way to connect terminals, such as cities, electronic components
or computers via roads, airlines, railways, wires or telephone lines.
4. MSTs are applied in routing algorithms for finding the most efficient path.

Prim’s Algorithm
Prim’s algorithm is a greedy algorithm that is used to form a minimum spanning tree for a connected weighted
undirected graph. In other words, the algorithm builds a tree that includes every vertex and a subset of the edges in
such a way that the total weight of all the edges in the tree is minimized.
For this, the algorithm maintains three sets of vertices which can be given as below:
• Tree vertices Vertices that are a part of the minimum spanning tree T.
• Fringe vertices Vertices that are currently not a part of T, but are adjacent to some tree vertex.
• Unseen vertices Vertices that are neither tree vertices nor fringe vertices fall under this category.
• Choose a starting vertex.
• Branch out from the starting vertex and during each iteration, select a new vertex and an edge. Basically,
during each iteration of the algorithm, we have to select a vertex from the fringe vertices in such a way that
the edge connecting the tree vertex and the new vertex has the minimum weight assigned to it.

Construct a minimum spanning tree of the graph given in Fig.

Step 1: Choose a starting vertex A.
Step 2: Add the fringe vertices (that are adjacent to A). The edges connecting the vertex and fringe vertices are
shown with dotted lines.
Step 3: Select an edge connecting the tree vertex and the fringe vertex that has the minimum weight and add the
selected edge and the vertex to the minimum spanning tree T. Since the edge connecting A and C has less weight,
add C to the tree. Now C is not a fringe vertex but a tree vertex.
Step 4: Add the fringe vertices (that are adjacent to C).

selected edge and the vertex to the minimum spanning tree T. Since the edge connecting C and B has less weight, add
B to the tree. Now B is not a fringe vertex but a tree vertex.
Step 6: Add the fringe vertices (that are adjacent to B).
selected edge and the vertex to the minimum spanning tree T. Since the edge connecting B and D has less weight, add
D to the tree. Now D is not a fringe vertex but a tree vertex.

Step 8: Note, now node E is not connected, so we will add it in the tree because a minimum spanning tree is one in
which all the n nodes are connected with n–1 edges that have minimum weight. So, the minimum spanning tree can
now be given as,
Construct a minimum spanning tree of the graph given in Fig. Start the Prim’s algorithm from vertex D.

Kruskal’s Algorithm
• Kruskal’s algorithm is used to find the minimum spanning tree for a connected weighted graph. The algorithm aims to
find a subset of the edges that forms a tree that includes every vertex.
• The total weight of all the edges in the tree is minimized. However, if the graph is not connected, then it finds a
minimum spanning forest. Note that a forest is a collection of trees. Similarly, a minimum spanning forest is a collection
of minimum spanning trees.
• Kruskal’s algorithm is an example of a greedy algorithm, as it makes the locally optimal choice at each stage with the
hope of finding the global optimum.
• In the algorithm, we use a priority queue Q in which edges that have minimum weight takes a priority over any other
edge in the graph. When the Kruskal’s algorithm terminates, the forest has only one component and forms a minimum
spanning tree of the graph.

Apply Kruskal’s algorithm on the graph given in Fig.
Initially, we have F = {{A}, {B}, {C}, {D}, {E}, {F}}
MST = {}
Q = {(A, D), (E, F), (C, E), (E, D), (C, D), (D, F), (A, C), (A, B), (B, C)}
Step 1: Remove the edge (A, D) from Q and make the following changes:
F = {{A, D}, {B}, {C}, {E}, {F}}
MST = {A, D}
Q = {(E, F), (C, E), (E, D), (C, D), (D, F), (A, C), (A, B), (B, C)}
Step 2: Remove the edge (E, F) from Q and make the following
changes:
F = {{A, D}, {B}, {C}, {E, F}}
MST = {(A, D), (E, F)}
Q = {(C, E), (E, D), (C, D), (D, F), (A, C), (A, B), (B, C)}

Step 3: Remove the edge (C, E) from Q and make the following changes:
F = {{A, D}, {B}, {C, E, F}}
MST = {(A, D), (C, E), (E, F)}
Q = {(E, D), (C, D), (D, F), (A, C), (A, B), (B, C)}
Step 4: Remove the edge (E, D) from Q and make the following changes:
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(C, D), (D, F), (A, C), (A, B), (B, C)}
Step 5: Remove the edge (C, D) from Q. Note that this edge does not connect different trees, so
simply discard this edge. Only an edge connecting (A, D, C, E, F) to B will be added to the MST.
Therefore,
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(D, F), (A, C), (A, B), (B, C)}

Step 6: Remove the edge (D, F) from Q. Note that this edge does not connect different trees, so simply discard this
edge. Only an edge connecting (A, D, C, E, F) to B will be added to the MST.
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(A, C), (A, B), (B, C)}
Step 7: Remove the edge (A, C) from Q. Note that this edge does not connect different trees, so simply discard this
edge. Only an edge connecting (A, D, C, E, F) to B will be added to the MST.
F = {{A, C, D, E, F}, {B}}
MST = {(A, D), (C, E), (E, F), (E, D)}
Q = {(A, B), (B, C)}
Step 8: Remove the edge (A, B) from Q and make the following changes:
F = {A, B, C, D, E, F}
MST = {(A, D), (C, E), (E, F), (E, D), (A, B)}
Q = {(B, C)}

Step 9: The algorithm continues until Q is empty. Since the entire forest has become one tree, all the remaining
edges will simply be discarded. The resultant MS can be given as shown below.
F = {A, B, C, D, E, F}
MST = {(A, D), (C, E), (E, F), (E, D), (A, B)}
Q={}

APPLICATIONS OF GRAPHS
Graphs are constructed for various types of applications such as:
• In circuit networks where points of connection are drawn as vertices and component wires become the edges of the
graph.
• In transport networks where stations are drawn as vertices and routes become the edges of the graph.
• In maps that draw cities/states/regions as vertices and adjacency relations as edges.
• In program flow analysis where procedures or modules are treated as vertices and calls to these procedures are drawn
as edges of the graph.
• Once we have a graph of a particular concept, they can be easily used for finding shortest paths, project planning, etc.
• In flowcharts or control-flow graphs, the statements and conditions in a program are represented as nodes and the
flow of control is represented by the edges.
• In state transition diagrams, the nodes are used to represent states and the edges represent legal moves from one state
to the other.
• Graphs are also used to draw activity network diagrams. These diagrams are extensively used as a project
management tool to represent the interdependent relationships between groups, steps, and tasks that have a significant
impact on the project.

An Activity Network Diagram (AND) also known as an Arrow Diagram or a PERT (Program Evaluation
Review Technique) is used to identify time sequences of events which are pivotal to objectives. It is also helpful
when a project has multiple activities which need simultaneous management.
ANDs help the project development team to create a realistic project schedule by drawing graphs that exhibit:
• the total amount of time needed to complete the project
• the sequence in which activities must be performed
• the activities that can be performed simultaneously
• the critical activities that must be monitored on a regular basis.

Data Structure of computer science and technology

Recommended

More Related Content

Similar to Data Structure of computer science and technology (20)

Recently uploaded (20)

Data Structure of computer science and technology