GRAPHS

Graph
A graph is a pictorial representation of a set of objects where some pairs of
objects are connected by links. A Graph is a non-linear data structure
consisting of nodes and edges. The nodes are sometimes also referred to as
vertices and the edges are lines or arcs that connect any two nodes in the
graph. More formally a Graph can be defined as,
A Graph consists of a finite set of vertices(or nodes) and set of Edges which
connect a pair of nodes.

In the above Graph, the set of vertices V = {0,1,2,3,4} and the set of edges
E = {01, 12, 23, 34, 04, 14, 13}.
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.

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)}. Note that there are five vertices or nodes and six edges in the
graph.
A graph can be directed or undirected. 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. Figure shows an undirected graph
because it does not give any information about the direction of the edges.

Figure shows a directed graph. 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)
Graph Terminology
A graph consists of: A set, V, of vertices (nodes)
A collection, E, of pairs of vertices from V called edges (arcs)
Edges, also called arcs, are represented by (u, v) and are either:
Directed if the pairs are ordered (u, v):u the origin ,v the destination
Undirected if the pairs are unordered
Then a graph can be:
Directed graph (di-graph) if all the edges are directed
Undirected graph (graph) if all the edges are undirected
Mixed graph if edges are both directed or undirected
End vertices or Endpoints:The two vertices joined by edge are called end vertices (or endpoints)
of that edge.
Origin:If a edge is directed, its first endpoint is said to be the origin of it.
Destination:If a edge is directed, its first endpoint is said to be the origin of it and the other
endpoint is said to be the destination of that edge.
Adjacent:If there is an edge between vertices A and B then both A and B are said to be
adjacent. In other words, vertices A and B are said to be adjacent if there is an edge between
them.
Outgoing Edge:A directed edge is said to be outgoing edge on its origin vertex.
Incoming Edge:A directed edge is said to be incoming edge on its destination vertex.
Degree:Total number of edges connected to a vertex is said to be degree of that vertex.
Indegree:Total number of incoming edges connected to a vertex is said to be indegree of that
vertex.
Outdegree:Total number of outgoing edges connected to a vertex is said to be outdegree of that
vertex.
Parallel edges or Multiple edges:If there are two undirected edges with same end vertices and
two directed edges with same origin and destination, such edges are called parallel edges or
multiple edges.
Self-loop:Edge (undirected or directed) is a self-loop if its two endpoints coincide with each
other.
Simple Graph:A graph is said to be simple if there are no parallel and self-loop edges.
Path:A path is a sequence of alternate vertices and edges that starts at a vertex and ends at
Graph Representations
There are three common ways of storing graphs in the computer’s memory. They are:
Sequential representation by using an adjacency matrix.
Linked representation by using an adjacency list that stores the neighbours of a node using
a linked list.
Adjacency multi-list which is an extension of linked representation.
Adjacency Matrix Representation
An adjacency matrix is used to represent which nodes are adjacent to one another. By
definition, two nodes are said to be adjacent if there is an edge connecting them
In an adjacency matrix, the rows and columns are labelled by graph vertices. An entry aij in
the adjacency matrix will contain 1, if vertices vi and vjare adjacent to each other. However,
if the nodes are not adjacent, aij will be set to zero

Since an adjacency matrix contains only 0s and 1s, it is called a bit matrix or a Boolean
matrix. The entries in the matrix depend on the ordering of the nodes in G. Therefore, a
change in the order of nodes will result in a different 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 4vertices 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 graph representation...
Adjacency List Representation
An adjacency list is another way in which graphs can be represented in the computer’s
memory.
This structure consists of a list of all nodes in G. Furthermore, every node is in turn linked to
its own list that contains the names of all other nodes that are adjacent to it.
The key advantages of using an adjacency list are:
It is easy to follow and clearly shows the adjacent nodes of a particular node.
It is often used for storing graphs that have a small-to-moderate number of edges. That is,
an adjacency list is preferred for representing sparse graphs in the computer’s memory;
otherwise, an adjacency matrix is a good choice.
Adding new nodes in G is easy and straightforward when G is represented using an
adjacency list.
Adding new nodes in an adjacency matrix is a difficult task, as the size of the matrix needs
to be changed and existing nodes may have to be reordered.
Consider the graph given in Fig, and see how its adjacency list is stored in the memory.
For a directed graph, the sum of the lengths of all adjacency lists is equal to the number of
edges in G.
However, for an undirected graph, the sum of the lengths of all adjacency lists is
equal to twice the number of edges in G because an edge (u, v) means an edge
from node u to v as well as an edge from vto u.
Adjacency lists can also be modified to store weighted graphs. Let us now see an
adjacency list for an undirected graph as well as a weighted graph.
This is shown in Fig
This representation can also be implemented using an array as follows..

Adjacency Multi-list Representation

Graphs can also be represented using multi-lists which can be said to be modified
version of adjacency lists. Adjacency multi-list is an edge-based rather than a
vertex-based representation of graphs. A multi-list representation basically consists
of two parts—a directory of nodes’ information and a set of linked lists storing
information about edges. While there is a single entry for each node in the node
directory, every node, on the other hand, appears in two adjacency lists (one for the
node at each end of the edge). For example, the directory entry for node i points to
the adjacency list for node i. This means that the nodes are shared among several
lists.
In a multi-list representation, the information about an edge (vi, vj) of an undirected
graph can be stored using the following attributes:
vi: A vertex in the graph that is connected to vertex vj by an edge.
vj: A vertex in the graph that is connected to vertex vi by an edge.
Link i for vi: A link that points to another node that has an edge incident on vi.
Link j for vi: A link that points to another node that has an edge incident on vj.
Consider the undirected graph given in Fig.

The adjacency multi-list for the graph can be given as:

Using the adjacency multi-list given above, the adjacency list for vertices can be
constructed as shown below:
Graph Operations
1. Breadth-first search
2. Depth-first search
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.
Example : Consider the graph G given in Fig. The adjacency list of G is also given.
Assume that Grepresents 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.
Solution
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.
Features of Breadth-First Search Algorithm

Space complexity In the breadth-first search algorithm, all the nodes at a particular level must be
saved until their child nodes in the next level have been generated. The space complexity is
therefore proportional to the number of nodes at the deepest level of the graph.

Completeness Breadth-first search is said to be a complete algorithm because if there is a

solution, breadth-first search will find it regardless of the kind of graph. But in case of an infinite
graph where there is no possible solution, it will diverge.

Optimality Breadth-first search is optimal for a graph that has edges of equal length, since it
always returns the result with the fewest edges between the start node and the goal node. But
generally, in real-world applications, we have weighted graphs that have costs associated with
each edge, so the goal next to the start does not have to be the cheapest goal available.

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.
DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a
graph without loops. We use Stack data structure with maximum size of total
number of vertices in the graph to implement DFS traversal.
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
Example 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.
Solution
(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
(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
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.
Features of Depth-First Search Algorithm
Space complexity The space complexity of a depth-first search is lower than that of a
breadth_x0002_first search.
Time complexity The time complexity of a depth-first search is proportional to the number of
vertices plus the number of edges in the graphs that are traversed. The time complexity can be
given as (O(|V| + |E|)).
Completeness Depth-first search is said to be a complete algorithm. If there is a solution,
depth_x0002_first search will find it regardless of the kind of graph. But in case of an infinite
graph, where there is no possible solution, it will diverge.
Applications of Depth-First Search Algorithm
Depth-first search is useful for:
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.