Unit-5

GRAPH:
A Graph is a non-linear data structure that is the same as the mathematical (discrete
mathematics) concept of graphs, 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.
Graphs are used to represent the arbitrary relationship among objects. It can be either directed
or undirected.

Consider the graph

G= (V, E)
V (G) = Vertices of Graph G
E (G) = Edges of Graph G

then,
V(G)={A,B,C,D,E,F}
E(G)={(AB),(AC),(BD),(BC),(DE),(DF),(EF)}

GRAPH TERMINOLOGIES:
● Path: A path can be defined as the sequence of nodes that are followed in order to
reach some terminal node V from the initial node U.
 ● Closed Path: A path will be called a closed path if the initial node is the same as a
terminal node. A path will be closed path if V0=VN.

● Simple Path: A path that does not repeat vertices is called a simple path, then such
path P is called a 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.

MOST COMMON TYPES OF GRAPHS:

There are several types of graphs available, but some graphs are more commonly used, they
are:
● Directed graph
● Undirected graph
● Weighted graph
● Unweighted graph
 Following are the list of graphs have in graph data structure:

[Link] GRAPH NAME [Link] GRAPH NAME

1 Null graph 11 Acyclic graph

2 Trivial Graph 12 Finite graph

3 Non-directed Graph 13 Infinite graph

4 Directed Graph 14 Bipartite graph

5 Connected Graph 15 Planar graph

6 Disconnect graph 16 Simple graph

9 Cycle graph 17 Euler graph

10 Cyclic graph 28 Hamiltonian graph

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. An undirected graph is shown in the following figure
since its edges are not attached with any of the directions. 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.

WEIGHTED AND UNWEIGHTED GRAPH:

 A weighted graph is a graph in which each branch is given a numerical weight. A
weighted graph is therefore a special type of labelled graph in which the labels are numbers
(which are usually taken to be positive). Whereas Unweighted graph doesn’t have any
numerical weight to it.

Representations of Graph
Here are the two most common ways to represent a graph :
1. Adjacency Matrix
2. Adjacency List

Adjacency Matrix
An adjacency matrix is a way of representing a graph as a matrix of boolean (0’s and
1’s).
Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n]
having dimension n x n.
 ● If there is an edge from vertex i to j, mark adjMat[i][j] as 1.
● If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

Representation of Undirected Graph to Adjacency Matrix:

The below figure shows an undirected graph. Initially, the entire Matrix is initialized to 0.
If there is an edge from source to destination, we insert 1 to both cases
(adjMat[destination] and adjMat[destination]) because we can go either way.

Undirected Graph to Adjacency Matrix

Representation of Directed Graph to Adjacency Matrix:

The below figure shows a directed graph. Initially, the entire Matrix is initialized to 0. If
there is an edge from source to destination, we insert 1 for that particular
adjMat[destination].
Directed Graph to Adjacency Matrix

Adjacency List
An array of Lists is used to store edges between two vertices. The size of array is equal to
the number of vertices (i.e, n). Each index in this array represents a specific vertex in the
graph. The entry at the index i of the array contains a linked list containing the vertices
that are adjacent to vertex i.
Let’s assume there are n vertices in the graph So, create an array of list of size n as
adjList[n].
● adjList[0] will have all the nodes which are connected (neighbour) to vertex 0.
● adjList[1] will have all the nodes which are connected (neighbour) to vertex 1
and so on.

Representation of Undirected Graph to Adjacency list:

The below undirected graph has 3 vertices. So, an array of list will be created of size 3,
where each indices represent the vertices. Now, vertex 0 has two neighbours (i.e, 1 and
2). So, insert vertex 1 and 2 at indices 0 of array. Similarly, For vertex 1, it has two
neighbour (i.e, 2 and 1) So, insert vertices 2 and 1 at indices 1 of array. Similarly, for
vertex 2, insert its neighbours in array of list.
Undirected Graph to Adjacency list

Representation of Directed Graph to Adjacency list:

The below directed graph has 3 vertices. So, an array of lists will be created of size 3,
where each indices represent the vertices. Now, vertex 0 has no neighbors. For vertex 1,
it has two neighbors (i.e, 0 and 2) So, insert vertices 0 and 2 at indices 1 of array.
Similarly, for vertex 2, insert its neighbors in an array of lists.

GRAPH TRAVERSALS:
 Graph traversal is a technique used for a searching vertex in a graph. The graph traversal
is also used to decide the order of vertices is visited in the search process. A graph traversal
finds the edges to be used in the search process without creating loops. That means using
graph traversal we visit all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)
2. BFS (Breadth-First Search)

DEPTH FIRST SEARCH:

Depth First Search (DFS) algorithm traverses a graph in a depth ward 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 the final result. Spanning Tree is
a graph without loops. We use a Stack data structure with a maximum size of a total number of
vertices in the graph to implement DFS traversal.

ALGORITHM:
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 a 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 the 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 backtracking 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 the final spanning tree by removing
unused edges from the graph

EXAMPLE:
As in the example given above, the DFS algorithm traverses from S to A to D to G to E to B first,
then to F and lastly to C. It employs the following rules.
● Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Push it in a
stack.
● 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.
BREADTH FIRST SEARCH:
Breadth-First Search (BFS) algorithm traverses a graph in a bread toward 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 the final result. Spanning Tree is
a graph without loops. We use a Queue data structure with a maximum size of a total number
of vertices in the graph to implement BFS traversal.
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 a 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 the queue becomes empty.
● Step 6 - When the queue becomes empty, then produce the final spanning tree by
removing unused edges from the graph.

EXAMPLE:
As in the example given above, the 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.
Divide and Conquer Introduction
Divide and Conquer is an algorithmic pattern. In algorithmic methods, the design
is to take a dispute on a huge input, break the input into minor pieces, decide the
problem on each of the small pieces, and then merge the piecewise solutions into
a global solution. This mechanism of solving the problem is called the Divide &
Conquer Strategy.
Divide and Conquer algorithm consists of a dispute using the following three
steps.

1. Divide the original problem into a set of subproblems.

2. Conquer: Solve every subproblem individually, recursively.
3. Combine: Put together the solutions of the subproblems to get the
solution to the whole problem.

Generally, we can follow the divide-and-conquer approach in a three-step

process.
Examples: The specific computer algorithms are based on the Divide & Conquer
approach:

1. Maximum and Minimum Problem

2. Binary Search
3. Sorting (merge sort, quick sort)
4. Tower of Hanoi.

Fundamental of Divide & Conquer Strategy:

There are two fundamental of Divide & Conquer Strategy:

1. Relational Formula
2. Stopping Condition

1. Relational Formula: It is the formula that we generate from the given

technique. After generation of Formula we apply D&C Strategy, i.e. we break the
problem recursively & solve the broken subproblems.

2. Stopping Condition: When we break the problem using Divide & Conquer
Strategy, then we need to know that for how much time, we need to apply divide
& Conquer. So the condition where the need to stop our recursion steps of D&C
is called as Stopping Condition.

Applications of Divide and Conquer Approach

Binary Search
Merge Sort
Closest Pair of Points
Cooley-Tukey Fast Fourier Transform (FFT) algorithm
Strassen's Algorithm