UNIT V

Searching and sorting

Sorting - An Introduction, Bubble Sort, Insertion Sort, Merge Sort
Searching - An Introduction, Linear or Sequential Search, Binary Search, Indexed Sequential Search.
Graphs: Introduction to Graphs, Terms Associated with Graphs, Sequential Representation of Graphs, Linked
Representation of Graphs, Traversal of Graphs, Spanning Trees, Shortest Path, Application of Graphs.

SORTING
Sorting refers to the technique of arranging and rearranging of data in some specific order. A collection of
records called a list where every record has one or more fields ..... The records are then arranged in ascending
or descending order depending on the numerical value of the key.
Sorting is the process of arranging data into meaningful order, so that we can analyze it more effectively and
efficiently. Sorting can be done for text data into alphabetical order, and numeric data into numerical order both
are from ascending or descending.
Sorting refers to arrangement of data items either in ascending order or in descending order. Sorting is the
most primitive operation in data organization.

In general, to perform binary search technique among n elements, then we need to arrange
these elements in one order. There are several kinds of sorting algorithms.
1. Bubble Sort
2. Selection Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort
6. Heap Sort
1. BUBBLE SORT
It is the most easiest sorting algorithms used with small number of elements.
In bubble sort technique, each time the consecutive elements are compared and swapping
takes place if necessary
i.e., a[0] is compared with a[1], a[1] is compared with a[2] and so on.
At the end of pass-1(iteration) the highest element of the list will be in its proper
position i.e., a[n-1] is filled with highest element, again we have to repeat the same
procedure for remaining n-1 elements. At the end of each iteration we found that the
consecutive highest element will get their proper place.
Let us consider the following example to implement bubble sort with an array a of 5 elements.

PASS-1:
In this pass a[0] is compared with a[1], a[1] is compared with a[2], a[2] is compared with a[3],
a[3] is compared with a[4]. Whenever greater than condition is true then swapping of those
two elements willbe performed.
 PASS-2:
In this pass a[0] is compared with a[1], a[1] is compared with a[2], a[2] is compared
with a[3].Whenever greater than condition is true then swapping of those two elements will be
performed.

PASS-3:
In this pass a[0] is compared with a[1], a[1] is compared with a[2]. Whenever greater than
condition istrue then swapping of those two elements will be performed.

PASS-4:
In this pass a[0] is compared with a[1]. Whenever greater than condition is true then
swapping ofthose two elements will be performed.

As the end of pass-4 the 4th highest element is in a[1] position. The number of
comparisons in pass-4 is 1. Thetotal number of passes is 4 and total number of comparisons
in all the passes is 10.
If there are n elements in the array then the total number of comparisons required for
bubble sort is n(n-1)/2.

ALGORITHM:
Step-1: Read list of elements into an array of size n.
Step-2: loop for i=0 to n-1 each time increase i by 1
Step-3: loop for j=0 to n-i-1 each time increase j by 1
Step-4: if a[j]>a[j+1] then
temp = a[j]
a[j] = a[j+1]
a[j+1] = temp
Step-5: exit
program to sort an array using Bubble Sort Algorithm.

#include <stdio.h>
#include <conio.h>
void main()
{
int a[15],i,j,n,temp;
clrscr();
printf("\nENTER THE SIZE OF ARRAY:") ;
scanf("%d",&n);
printf("\nENTER VALUES FOR THE ARRAY:\n");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
printf("\nTHE SORTED ARRAY IS:\n");
for(i=0;i<n;i++)
printf("%d ",a[i]);
getch();
}

2. SELECTION SORT
It is the most easiest sorting algorithm used with small number of elements. In selection sort
techniques, each time one element is compared with all the remaining elements and swapping
takes place if necessary,
i.e., a[0] iscompared with a[1],a[2],..a[n-1] and
a[1] is compared with a[2],a[3]… and so on…. At the end of pass-1, the lowest
element of the list will be in its proper position i.e., a[0].
Again we have to repeat the same process with a[1] for remaining elements. At the
end of each iteration we findthat the consecutive lowest element will be placed in their proper
places.
Let us consider the following example to implement selection sort with an array of 5
elements.

PASS-1:
In this pass a[0] is compared with a[1],a[2],a[3] and a[4]. If a[0] greater than any of the element
then swapping will be takes place.
 PASS-2:
In this pass a[1] is compared with a[2],a[3] and a[4]. If a[1] greater than any of the element then
swapping will be takes place.

PASS-3:
In this pass a[2] is compared with a[3] and a[4]. If a[2] is greater than any of the element then
swapping will be takes place.

PASS-4:
In this pass a[3] is compared with a[4]. If a[3] is greater than a[4] then swapping will be done.

Algorithm:
Step-1: Read a list of elements into an array of size n.
Step-2: loop i=0 to n-1 each time increment i by 1
Step-3: loop j=i+1 to n-1 each time increment j by 1
Step-4: if a[i] > a[j] then
temp=a[i]
a[i]=a[j]
a[j]=temp
Step-5: Exit

Program on Selection Sort

#include <stdio.h>
#include <conio.h>
void main()
{
int array[10];
int i, j, N, temp;
int findmax(int b[10], int k);
/* function declaration */
void exchang(int b[10], int k);
clrscr();
printf("Enter the value of N\n");
scanf("%d",&N);
printf("Enter the elements one by one\n");
for (i=0; i<N ; i++)
{
 scanf("%d",&array[i]);
}
printf("Input array elements\n");
for (i=0; i<N ; i++) {
printf("%d\n",array[i]);
}
/* Selection sorting begins */
exchang(array,N);
printf("Sorted array is...\n");
for (i=0; i< N ; i++)
{
printf("%d\n",array[i]);
}
}
/* End of main*/
/* function to find the maximum value */
int findmax(int b[10], int k)
{
int max=0,j;
for (j = 1; j <= k; j++)
{
if ( b[j] > b[max])
{
max = j;
}
}
return(max);
}
void exchang(int b[10],int k)
{
int temp, big, j;
for ( j=k-1; j>=1; j--)
{
big = findmax(b,j);
temp = b[big];
b[big] = b[j];
b[j] = temp;
}
return;
}

3. INSERTION SORT:
It is another kind of most efficient sorting algorithm. This algorithm begins with taking first
element of the listas in its proper place i.e, in sorted list and the remaining all elements will be
considered as unsorted list.
Then first element of the unsorted list will be compared with sorted list and if it is less than
the value in sorted list then swapping will be performed. This process will be continued until
unsorted list will become empty.
Let us consider the following list in to an array of size 5.

First we will split the list into two parts as follows.

First element will be considered as sorted list and all the remaining will be considered as
unsorted list.
 PASS-1:
In this pass a[1] will be a[0]. Since a[0] < a[1] then a[1] will be taken into sorted list without
swapping.

PASS-2:
In this pass a[2] is compared with a[1]. Since a[1] > a[2] then swapping will be performed.

After swapping a[1] and a[0] are compared. Since a[0] > a[1] then again swapping will be
performed.

PASS-3
In this pass a[3] is compared with a[2]. Since a[2] > a[3] then swapping will be performed.
After swapping a[2] is compared with a[1]. Since a[1] < a[2] then this will be completed.

PASS-4
In this pass a[4] is compared with a[3]. Since a[3] > a[4] swapping will be performed.

After swapping a[3] is compared with a[2]. Since a[2] >a[3] again these two elements will be
swapped.

After swapping a[2] is compared with a[1]. Since a[1] >a[2] again these two elements will be
swapped.

After swapping a[1] is compared with a[0]. Since a[0] >a[1] again these two elements will be
swapped.

There are no more elements left to compare. So 7 is placed at a[0].

Algorithm:
Step-1: Read a list values into an array of size n.
Step-2: loop for i=1 to n-1 each time increment i by 1.
Step-3: set value=a[i] and place =i
Step-4: Repeat step-5
until place > 0 and a[place-1] > value
Step-5: a[place]=a[place-1]
Place=place-1
Step-6: a[place]=value
Step-7: Exit
Program on Insertion sort using functions
#include<stdio.h>
#include<conio.h>
void inst_sort(int []);
void main()
{
int num[5],count;
clrscr();
printf("\nEnter the Five Elements to sort:\n");
for (count=0;count<5;count++)
scanf("%d",&num[count]);
inst_sort(num);
printf("\n\nElements after sorting: \n");
for (count=0;count<5;count++)
printf("%d\n",num[count]);
getch();
}
// Function for Insertion Sorting
void inst_sort(int num[])
{
int i,j,k;
for (j=1;j<5;j++)
{
k=num[j];
for (i=j-1;i>=0 && k<num[i];i--)
num[i+1]=num[i];
num[i+1]=k;
}
}

4. QUICK SORT:
This is the most efficient and fastest sorting procedure when compared to all other sorting
algorithms. This sorting algorithm uses divide and conquer approach of the elements of the
array to arrange them either in ascending order or in descending order.
• In this algorithm the array will be portioned into two parts based on pivot element.
• On each step the pivot element will be placed in correct location and hence the array will
be divided into two parts. Those are before pivot element and after the pivot element.
• The same process is repeated for both parts and therefore again these two parts will be
divided and same process is repeated for these subparts until the size of the sub part
become 1.
• It is very clear that the algorithm is completely based on portioning approach for the pivot
element.

Algorithm:
Step-1 : Read a list of values into an array of size n.
Step-2 : set i=low and j=high+1
Step-3 : if low < high
Set pivot=a[low]
Step-3.1 : Repeat
while a[i] < pivot and i < hight, i++
Step-3.2 : Repeat while a[j]>pivot and j>=high, j - -
Step-3.3 : if(i<j) then
temp=a[i]
a[i]=a[j]
a[j]=Temp
Repeat until 3.1, 3.2, 3.3 otherwise stop the loop
Step-3.4 : swap pivot and a[j]
 Quick(a, low, j-1)
Quick(a, j+1, high)
Step-4 : Exit

Program using Quick Sort Algorithm.

#include <stdio.h>
#include <conio.h>
void qsort();
int n;
void main()
{
int a[100],i,l,r;
clrscr();
printf("\nENTER THE SIZE OF THE ARRAY: ");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("\nENTER NUMBER-%d: ",i+1);
scanf("%d",&a[i]);
}
printf("\nTHE ARRAY ELEMENTS BEFORE SORTING: \n");
for(i=0;i<n;i++)
{
printf("%5d",a[i]);
}
l=0;
r=n-1;
qsort(a,l,r);
printf("\nTHE ARRAY ELEMENTS AFTER SORTING: \n");
for(i=0;i<n;i++)
printf("%5d",a[i]);
getch();
}
void qsort(int b[],int left,int right)
{
int i,j,p,tmp,finished,k;
if(right>left)
{
i=left;
j=right;
p=b[left];
finished=0;
while (!finished)
{
do
{
++i;
}
while ((b[i]<=p) && (i<=right));
while ((b[j]>=p) && (j>left))
{
--j;
}
if(j<i)
finished=1;
else
{
tmp=b[i];
b[i]=b[j];
 b[j]=tmp;
}
}
tmp=b[left];
b[left]=b[j];
b[j]=tmp;
qsort(b,left,j-1);
qsort(b,i,right);
}
return;
}

5. MERGE SORT
Merge sort technique can be implemented in two ways.
1. We can take two sorted lists and then form a new sorted list by arranging the
two sorted lists into onelist.
2. We will divide the list into two parts until the sub-list contains single values and
then merging them in a sorted order. While merging place lower values in left
hand side and larger values in right hand side.

44 29 25 35 56 77 42 39

44 29 25 35 56 77 42 39

44 29 25 35 56 77 42 39

44 29 25 35 56 77 42 39

29 44 25 35 56 77 39 42

25 29 35 44 39 42 56 77

25 29 35 39 42 44 56 77
 Algorithm:
Step-1: Read a list of elements into an array of size n
Step-2: Divide the unsorted list into two sub-lists of about half the size
until the sub-list contains single element.
Step-3: Sort each sub-list recursively by reapplying merge sort
Step-4: Merge the two lists into one sorted list
until the final list contains n elements.
Step-5: Exit

Program on Merge Sort using functions

#include <stdio.h>
#include <stdlib.h>
#define MAX_ARY 10
void merge_sort(int x[], int end, int start);
int main(void) {
int ary[MAX_ARY];
int j = 0;
printf("\n\nEnter the elements to be sorted: \n");
for (j=0;j<MAX_ARY;j++)
scanf("%d",&ary[j]);
/* array before mergesort */
printf("Before :");
for (j = 0; j < MAX_ARY; j++)
printf(" %d", ary[j]);
printf("\n");
merge_sort(ary, 0, MAX_ARY - 1);
/* array after mergesort */
printf("After Merge Sort :");
for (j = 0; j < MAX_ARY; j++)
printf(" %d", ary[j]);
printf("\n");
getch();
}
/* Method to implement Merge Sort*/
void merge_sort(int x[], int end, int start) {
int j = 0;
const int size = start - end + 1;
int mid = 0;
int mrg1 = 0;
int mrg2 = 0;
int executing[MAX_ARY];
if(end == start)
return;
mid = (end + start) / 2;
merge_sort(x, end, mid);
merge_sort(x, mid + 1, start);
for (j = 0; j < size; j++)
executing[j] = x[end + j];
mrg1 = 0;
mrg2 = mid - end + 1;
for (j = 0; j < size; j++) {
if(mrg2 <= start - end)
if(mrg1 <= mid - end)
if(executing[mrg1] > executing[mrg2])
x[j + end] = executing[mrg2++]; else
x[j + end] = executing[mrg1++]; else
x[j + end] = executing[mrg2++]; else
x[j + end] = executing[mrg1++];
}
}
6. Heap Sort
Heap sort is one of the sorting algorithms used to arrange a list of elements in order. Heap
sort algorithm uses one of the tree concepts called Heap Tree. In this sorting algorithm, we
use Max Heap to arrange list of elements in Descending order and Min Heap to arrange list
elements in ascending order.
 Algorithm:
The Heap sort algorithm to arrange a list of elements in ascendingorder
Step 1 : Construct a Binary Tree with given list of Elements.
Step 2 : Transform the Binary Tree into Min Heap.
Step 3 : Delete the root element from Min Heap using Heapify method.
Step 4 : Put the deleted element into the Sorted list.
Step 5 : Repeat the same until Min Heap becomes empty.
Step 6 : Display the sorted list.

Program on Heap Sorting using functions

#include<stdio.h>
void heapsort(int[],int);
void heapify(int[],int);
void adjust(int[],int);
main() {
int n,i,a[50];
system("clear");
printf("\nEnter the limit:");
scanf("%d",&n);
printf("\nEnter the elements:");
for (i=0;i<n;i++)
scanf("%d",&a[i]);
heapsort(a,n);
printf("\nThe Sorted Elements Are:\n");
for (i=0;i<n;i++)
printf("\t%d",a[i]);
printf("\n");
}
void heapsort(int a[],int n) {
int i,t;
heapify(a,n);
for (i=n-1;i>0;i--) {
t = a[0];
a[0] = a[i];
a[i] = t;
adjust(a,i);
}
}
void heapify(int a[],int n) {
int k,i,j,item;
for (k=1;k<n;k++) {
item = a[k];
i = k;
j = (i-1)/2;
while((i>0)&&(item>a[j])) {
a[i] = a[j];
i = j;
j = (i-1)/2;
}
a[i] = item;
}
}
 void adjust(int a[],int n) {
int i,j,item;
j = 0;
item = a[j];
i = 2*j+1;
while(i<=n-1) {
if(i+1 <= n-1)
if(a[i] <a[i+1])
i++;
if(item<a[i]) {
a[j] = a[i];
j = i;
i = 2*j+1;
} else
break;
}
a[j] = item;
}

SEARCHING:
Finding the element whether the given element is present in the list or not is called searching.
It is the most important operation in the field of computer science. Searching means finding the
required element from a group of elements. The searching element is used as a key element.
There are two types of searching mechanisms. They are
1. Linear/ Sequential Search
2. Binary Search
1. LINEAR or SEQUENTIAL SEARCH
As the name implies, the linear search works in a sequential order from the first element to the
required element found or till to the end of the list. The linear search compares the key
element with the group elements one by one until either a match has been found or the list
becomes end.
Let us consider the following example.

Let, Search key=29.

1. The search process starts at a[0], which is compared with key. Since a[0] ≠
key we move to the nextelement.
2. Now a[1] is compared with key element. Since a[1] ≠ key we move on to the next
element.
3. Now a[2] is compared with key element. Since a[2] = key we stop the search
process.

Algorithm:
Step-1: Read list of element into array a with size n.
Step-2: set i = 0 , flag = 0
Step-3: Repeat
while(i<n)
if(a[i] = key) then
set flag=1 and break the loop.
set i=i+1
 Step-4: if flag= = 1 then
Display “element found”
else
Display “element not found”
Step-5: Exit

Program : Linear or Sequential Search

#include <stdio.h>
#include <conio.h>
main()
{
int arr[]={12,23,78,98,67,56,45,19,65,9},key,i,flag=0;
clrscr();
printf("\nENTER A NUMBER: ");
scanf("%d",&key);
for(i=0;i<10;i++)
{
if(key==arr[i])
flag=1;
}
if(flag==1)
printf("\nTHE NUMBER %d EXISTS IN THE ARRAY",key);
else
printf("\nTHE NUMBER %d DOES NOT EXIST IN THE ARRAY",key);
getch();
}

Output :

2. BINARY SEARCH
It is a divide and conquer technique. In binary search, the search process always focused on
middleelement of the list. In-order to perform binary search, the elements of the list should be
arranged in a sortedorder.
In binary search, first we calculate the location of the middle element. Then that element
is comparedwith key element. Then any one of the following three cases may occur.
1. If the key element is equal to the middle element, then we conclude that the
element was found and willstop the searching process.
2. If the key element is less than middle element then we divide the array from the
first element to middle element and repeat the same process by calculating
middle element.
3. If the key element is greater than middle element, then we divide the array from
middle element to last element and repeat the same process by calculating
middle element.
 Algorithm:
Step-1: Read list of elements into array a with size n in sorted order.
Step-2: set start=0, end=n-1, flag=0
Step-3: Repeat
while (start<=end)
Calculate mid=(start+end)/2
If(a[mid]>key) then end=mid-1
If(a[mid]<key) then start mid+1
If(a[mid])==key then
set flag=1 and break the loop
Step-4: if(flag==1) then
Display” element found”
else
Display “element not found”
Step-5 : Exit

Program : Binary Search using functions

#include <stdio.h>
#include <conio.h>
void sort(int *);
int search(int *,int);
void main()
{
int a[10],i,j,temp,key,flag;
clrscr();
for(i=0;i<10;i++)
{
printf("\nENTER NUMBER-%d: ",i+1);
scanf("%d",&a[i]);
}
sort(a);
printf("\nTHE SORTED ARRAY IS: ");
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("\nENTER A NUMBER TO SEARCH: ");
scanf("%d",&key);
flag=search(a,key);
if(flag==1)
printf("\nTHE NUMBER %d EXISTS",key);
else
printf("\nTHE NUMBER %d DOES NOT EXIST ARRAY",key);
getch();
}

void sort(int *x)

{
int i,j,temp;
for(i=0;i<10;i++)
{
for(j=i+1;j<10;j++)
{
if(x[i]>x[j])
{
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}
 }
}
int search(int *x,int k)
{
int low=0,high=10,mid,res=0;
while(high>=low)
{
mid=(high+low)/2;
if(k==x[mid])
{
res=1;
break;
}
else
{
if(k>x[mid])
low=mid+1;
else
high=mid-1;
}
}
return res;
}

3. INDEXED SEQUENTIAL SEARCH

In Indexed Sequential Search a sorted index is set aside in addition to the array. Each
element in the index points to a block of elements in the array or another expanded index. The
index is searched 1st then the array and guides the search in the array.
In this searching method, first of all, an index file is created, that contains some specific
group or division of required record when the index is obtained, then the partial indexing takes
less time cause it is located in a specified group.
Note: When the user makes a request for specific records it will find that index group first
where that specific record is recorded.

Explanation by diagram “Indexed Sequential Search”:

// C program for Indexed Sequential Search

#include <stdio.h>
#include <stdlib.h>
void indexedSequentialSearch(int arr[], int n, int k)
{
int elements[20], indices[20], temp, i, set = 0;
int j = 0, ind = 0, start, end;
for (i = 0; i < n; i += 3)
 {
// Storing element
elements[ind] = arr[i];
// Storing the index
indices[ind] = i;
ind++;
}
if (k < elements[0])
{
printf("Not found");
exit(0);
}
else
{
for (i = 1; i <= ind; i++)
if (k <= elements[i])
{
start = indices[i - 1];
end = indices[i];
set = 1;
break;
}
}
if (set == 0)
{
start = indices[i - 1];
end = n;
}
for (i = start; i <= end; i++)
{
if (k == arr[i])
{
j = 1;
break;
}
}
if (j == 1)
printf("Found at index %d", i);
else
printf("Not found");
}

// Driver code
void main()
{
int arr[] = { 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);

// Element to search
int k = 8;
indexedSequentialSearch(arr, n, k);
}

Output:
Found at index 2
GRAPHS
Graph is a non-linear data structure mainly used in the applications for finding shortest path
root. This data structure consists of number of non-empty set of vertices as well as edges.
(OR)
A graph can be defined as group of vertices and edges that are used to connect these
vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes) maintain any
complex relationship among them instead of having parent child relationship.

Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the set of vertices
and E(G) represents the set of edges which are used to connect these vertices.

A graph ‘G’ consists of a set of ‘V’ vertices (nodes) and set of ‘E’ edges (arcs)
To represent a graph G= {V, E}, here V is a non-empty set of vertices, E is a set of pairs of
vertices called edges.
Where V = {v1, v2,………vi};
E = {e1, e2, e3….ej}

Generally, graphs are mainly two types, they are

1. undirected graphs
2. directed graphs.

Fig. undirected graph Fig. directed graph

TERMINOLOGY:
Let us take a graph

1. Path:
The edges involved in connection between any pair of vertices is called path. In the above
example the edges AB,BD forms a path between the vertices A and D.
start vertex

End vertex
2. Isolated Vertex:
A vertex which does not have any edges connect to it os called isolated vertex. In the below

example D is called isolated vertex.

3. Undirected Graph:
A graph G(V,E) is called an undirected graph, if there is no specified direction for the edges.

4. Directed graph or Digraph:

A graph G(V,E) is said to be digraph, if the directions are specified for all edges.
5. In-degree of a graph:
For a directed graph, the number of edges incident with vertex is called its in-degree. The in-
degrees of vertices of the above graph is shown below.
In-Degree of
A is 0
B is 2
C is 1
D is 2
E is 2

6. Out-degree of a graph:
For a directed graph, the number of edges eliminating from a vertex is called out-degree. The
out-degree of vertices of the above graph is shown below.
Out-Degree of A is 2
B is 2
C is 1
D is 1
E is 1
 7. Loop (or) Cycle:
A path which starts from a vertex and ends with the same vertex forms a cycle.

8. Self-Loop:

A vertex which has an edge with itself is called as self loop.

9. Weighted Graph:
A graph G(V,E) is called a weighted graph, if there is a positive integer assigned to each and
every edges of a graph.

REPRESENTATION OF GRAPH IN MEMORY:

A graph in memory is represented in two ways.
1. Adjacency Matrix
2. Adjacent List

1. Adjacency Matrix:
In this representation, a graph is represented as a 2-dimensional array of size n x n, where n is
the number of vertices in the graph. If there is an edge between the two vertices then element
value is represented as value ‘1’, otherwise value ‘0’.
Consider the following digraph and its equivalent adjacency matrix

For a weighted graph instead of representing ‘1’ value we place its weight in the matrix.

Note: If the graph is an undirected graph, we obtain a matrix such as A ij = Aji for all i,j
such a matrix is called symmetric matrix.
 2. Adjacent List
The adjacency matrix representation contains more number of zero entries. A matrix with more
numberof zero elements is called as sparse matrix.
So, there is a lot of waste storage space. To overcome this problem, a graph is
represented with the help of linked list.

APPLICATIONS OF GRAPHS
Since they are powerful abstractions, graphs can be very important in modeling data.

• Social network graphs: Graphs that represent who knows whom, who communicates with
whom or other relationships in social structures
• Transportation networks: Graph networks are used by many map programs such as Google
maps, Bing maps and now Apple IOS 6 maps to find the best routes between locations.
• 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.
• 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.
• Network packet traffic graphs. Vertices are IP (Internet protocol) addresses and edges are the
packets that flow between them.
• Robot planning. Vertices represent states the robot can be in and the edges the possible
transitions between the states.
• 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.
• Semantic networks. Vertices represent words or concepts and edges represent the relationships
among the words or concepts.
• 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.
TRAVERSAL OF A GRAPH
A graph traversal means, visiting all the nodes of the graph. Graph traversal may be needed
in many of application areas and there may be many methods for visiting the vertices of the
graph. Many graph applications required to one to systematically examining the nodes and
edges of a graph.
There are two standard ways ie., is done
1) Breadth first search (BFS)
2) Depth first search (DFS)
Here, The breadth – first search will use a queue as an auxiliary structure to hold
nodes for future processing The depth – first search will use a stack.

1. BREADTH – FIRST SEARCH (BFS)

Breadth first search can be used to find the shortest distance between starting node and
the remaining nodes of the graph. This shortest distance is the minimum number of
edges traversed in order to travel from the starting node to the specific node being
examined.

The general idea behind a breadth – first search beginning at a starting node A
is as follows.
• First we examine the starting node A.
• Then we examine all the neighbors of A.
• After then we examine all the neighbors of the neighbors of A.
• And so on.
During the execution of our algorithm each node of a graph will be in one of 3
statuses called “STATUS” of the node.

STATUS 1: (Ready state): - The initialize state of the node.

STATUS 2: (Waiting state): - The node ‘n’ is on the queue waiting for processing.
STATUS 3: (Processed state):- The node ‘n’ has been processed.

Algorithm:
This algorithm executes a breadth – first search on a graph G beginning at a starting node A.
1. Initialize all nodes to the ready state (STATUS = 1)
2. Put the starting node A in QUEUE and change its status to the waiting state(STATUS = 2).
3. Repeat the steps 4 & 5until the queue is empty.
4. Remove the front node N of QUEUE. Process N and change the status of N
to the processed state(STATUS = 3).
5. Add to the rear of QUEUE all the neighbors of N that are in the steady state
(STATUS = 1), and change their status to the waiting state (STATUS = 2).
[End of Step3 loop.]
6. Exit.

The above algorithm will process only those nodes which are reachable from the
starting node A. Suppose one wants to examine all the nodes in the graph G. then the
algorithm must be modified so that it begins again with another node (which we will call B)
that is still in the ready state. This node B can be obtained by traversing the list of nodes.
Example:
Consider the graph G In fig. Suppose G represents the daily flights between cities some
airline, and suppose we want to fly from city A to city J with the minimum number of stops.
In other words, we want the minimum path P from A to J (where each edge has length 1).
The minimum path P can be found by using a breadth – first search beginning at city
A and ending when J is encountered. During the execution of the search, we will also keep
track of the origin of each edge by using an array ORIG together with the array QUEUE.

Adjacency Lists
A: F, C, B
F C B B: G, C
C: F
D: C
E: D,C,J
F: D
D E G G: C,E
J: D,K
K: E,G
J K

Fig. a. Fig. b

The steps of our search follow.

a. Initially, add A to QUEUE and add NULL to ORIG as follows:
FRONT = 1 QUEUE: A
REAR = 1 ORIG: Ø
b. Remove the front element A from QUEUE by setting FRONT:=FRONT + 1. and add to
QUEUE the neighbors of A as follows:
FRONT = 2 QUEUE: A, F, C, B
REAR = 4 ORIG: Ø, A, A, A
Note that the original A of each of the three edges is added to ORIG.
c. Remove the front element F from QUEUE by setting FRONT := FRONT +1, and add to
QUEUE the neighbors of F as follows:
FRONT = 3 QUEUE: A, F, C, B, D
REAR = 5 ORIG: Ø, A, A, A, F
d. Remove the front element C from QUEUE, and add to QUEUE the neighbors of
C(which are in the ready state) as follows:
FRONT = 4 QUEUE: A, F, C, B, D
REAR = 5 ORIG: Ø, A, A, A, F
Note that the neighbor F of C is not added to QUEUE, since F is not in the ready
state (because F has already been added to QUEUE).
e. Remove the front element B from QUEUE, and add to QUEUE the neighbors of
B(the ones in the ready state) as follows:
FRONT = 5 QUEUE: A, F, C, B, D,G
REAR = 6 ORIG: Ø, A, A, A, F,B
Note that only G is added to QUEUE, since the other neighbor, C is not in the ready state.
f. Remove the front element D from QUEUE, and add to QUEUE the neighbors of
 D(the ones in the ready state) as follows:
FRONT = 6 QUEUE: A, F, C, B, D, G
REAR = 6 ORIG: Ø, A, A, A, F, B
g. Remove the front element G from QUEUE, and add to QUEUE the neighbors of
G(the ones in the ready state) as follows:
FRONT = 7 QUEUE: A, F, C, B, D, G, E
REAR = 7 ORIG: Ø, A, A, A, F, B, G
h. Remove the front element E from QUEUE, and add to QUEUE the neighbors of
E(the ones in the ready state) as follows:
FRONT = 4 QUEUE: A, F, C, B, D, G, E, J
REAR = 5 ORIG: Ø, A, A, A, F, B, G, E
We stop as soon as J is added to QUEUE, since J is our final destination. We now
backtrack from J, using the array ORIG to find the path P. Thus
J E G B A

2. DEPTH FIRST SEARCH (DFS):

Depth First Search is an alternative to the breadth first search. The general idea behind
a depth – first search beginning at a starting node A is as follows.
• First we examine the starting node A.
• Then we examine each node N along a path P which begins at A; that is, we
process a neighbor of A,
• then a neighbor of a neighbor of A,
• and so on.
After coming to a “dead end,” that is, to the end of the path P, we backtrack on P until
we can continue along another path p’. And so on.
(This algorithm is similar to the inorder traversal of a binary tree, and the algorithm is also similar
to the way one might travel through a maze.)
The algorithm is very similar to the breadth – first search except now we use a
stack instead of the queue.

During the execution of our algorithm each node of a graph will be in one of three
statuses called “STATUS” of the node.
STATUS 1: (Ready state):- The initialize state of the node.
STATUS 2: (Waiting state):- The node ‘n’ is on the stack waiting for processing.
STATUS 3: (Processed state):- The node ‘n’ has been processed.

Algorithm:
This algorithm executes a Depth – first search on a graph G beginning at a starting node A.
1: Initialize all nodes to the ready state (STATUS 1)
2: Put the starting node ‘A’ in STACK and change its status to the waiting state
(STATUS 2)
3: Repeat steps 4 & 5 until STACK is empty.
4: Remove the front node ‘A’ of STACK. Process ‘A’ and change the status of ‘A’ to
the processed state (STATUS 3).
5: Add to the STACK of all the neighbors of node ‘A’ that are in the ready state and
change their status to the waiting state (STATUS 2).
6: Exist.
 Again, the above algorithm will process only those nodes which are reachable from
the starting node A. Suppose one wants to examine all the nodes in G. Then the
algorithm must be modified so that it begins again with another node which we will call
B – that is still in the ready state. This node B can be obtain by traversing the list of
nodes.

Example:
Consider the graph G in Fig. Suppose we want to find and print all the node reachable
from the node J (including J itself). One way to do this is to use a depth – first search of
G starting at the node J. the steps of our search follow.

a). Initially, push J onto the stack as flows:

STACK: J
b). Pop and print the top element J, and then push onto the stack all the neighbors of J
(those that are in the ready state) as follows:
Print J STACK: D, K
c). Pop and print the top element K, and then push onto the stack all the neighbors of
K(those that are in the ready state) as follows:
Print K STACK: D, E, G
d). Pop and print the top element G, and then push onto the stack all the neighbors
G(those in the ready state) as follows:
Print G STACK: D, E, C
Note that only C is pushed onto the stack, since the other neighbors, E, is not in the
ready state(because E has already been pushed onto the stack).
e). Pop and print the top element C, and then push onto the stack all the neighbors of C
(those in the ready state) as follows:
Print C STACK: D, E, F
f). Pop and print the top element F, and then push onto the stack all the neighbors of
F(those in the ready state) as follows:
Print FSTACK: D, E
Note that the only neighbor D of F is not pushed onto the stack, since D is not in the
ready state( because D has already been pushed onto the stack).
g). Pop and print the top element E, and push onto the stack all the neighbors of E(those
in the ready state) as follows:
Print E STACK: D

(Note that none of the three neighbors of E is in the ready state.)

h). Pop and print the top element D, and push onto the stack all the neighbors of D(those
in the ready state) as follows:
Print D STACK:
The stack is now empty, so the depth – first search of G starting at J is now
complete.

Accordingly, the nodes which were printed, J, K, G, C, F, E, D

SPANNING TREE
Spanning tree of the graph is an undirected graph consisting of only those edges that are
necessary to connect all the vertices in the original graph.
A spanning tree has a property that any pair of vertices they exists only one path
between them, in spanning tree travers from any edge make a unique cycle.

General Properties of Spanning Tree

Following are a few properties of the spanning tree connected to graph G −
1. A connected graph G can have more than one spanning tree.
2. All possible spanning trees of graph G, have the same number of
edges and vertices.
3. The spanning tree does not have any cycle (loops).
4. Removing one edge from the spanning tree will make the graph disconnected,
i.e. thespanning tree is minimally connected.
5. Adding one edge to the spanning tree will create a circuit or loop, i.e.
the spanning treeis maximally acyclic.
Mathematical Properties of Spanning Tree
1. Spanning tree has n-1 edges, where n is the number of nodes (vertices).
2. From a complete graph, by removing maximum e - n + 1 edges, we
can construct aspanning tree.
3. A complete graph can have maximum nn-2 number of spanning trees.

Applications of Spanning Tree

Spanning tree is basically used to find a minimum path to connect all nodes in a graph.
Common applications of spanning trees are −

Examples of spanning tree

The spanning trees for the above graph are

Minimum Spanning Trees:
For a weighted graph, the spanning tree which is formed with all the vertices of the graph whose
total cost is minimum among all the other spanning trees is called “minimal spanning tree”.
Obtaining a minimum cost spanning tree involves so much of work. In-order to simplify this
process, two algorithms are introducedthey are
1. Kruskal’s algorithm
2. Prim’s algorithm
The DFS and BFS traversals result in a spanning tree but it is not guaranteed to be a minimum
spanning tree.
1. KRUSKAL’S ALGORITHM:
The algorithm was introduced by a mathematician [Link].
Algorithm:
Step-1: Initialize all the vertices with no edges.
Step-2: Maintain a list of edges I an increasing order of weights.
Step-3: Choose edges from list one by one and add it to the tree if it doesn’t form a cycle.
Step-4: Repeat step 3 until (n-1) edges are added to the tree.

Implementation:

Let us consider the following weighted graph with 6 vertices.

1. Initialize all the vertices with no edges.

Edge Weight Status

BE 1 0
AB 2 0
DF 3 0
AE 3 0
AF 4 0
CF 4 0
BD 5 0
CD 6 0
ED 6 0
BC 7 0
2. Least cost edge is BE.

Edge Weight Status

BE 1 1(select)
AB 2 0
DF 3 0
AE 3 0
AF 4 0
CF 4 0
BD 5 0
CD 6 0
ED 6 0
BC 7 0

3. Next least cost edge is AB.

Edge Weight Status

BE 1 1(select)
AB 2 1(select)
DF 3 0
AE 3 0
AF 4 0
CF 4 0
BD 5 0
CD 6 0
ED 6 0
BC 7 0

4. The next least cost edge is DF.

Edge Weight Status

BE 1 1(select)
AB 2 1(select)
DF 3 1(select)
AE 3 0
AF 4 0
CF 4 0
BD 5 0
CD 6 0
ED 6 0
BC 7 0

5. Next least cost edge is AE. But it forms a cycle. So it is rejected.

 6. The next least cost edge is AF.

Edge Weight Status

BE 1 1(select)
AB 2 1(select)
DF 3 1(select)
AE 3 0(reject)
AF 4 1(select)
CF 4 0
BD 5 0
CD 6 0
ED 6 0
BC 7 0

7. Next least cost edge is CF.

Edge Weight Status

BE 1 1(select)
AB 2 1(select)
DF 3 1(select)
AE 3 0(reject)
AF 4 1(select)
CF 4 1(select)
BD 5 0
CD 6 0
ED 6 0
BC 7 0

8. The one more edge inclusion forms a cycle. So the process is stopped here

Therefore the total cost of minimum spanning tree is 1+2+3+4+4=14.

2. PRIM’S ALGORITHM
This algorithm was introduced by [Link].
Algorithm:
Step-1: Initialize all the vertices with no edges.
Step-2: Take a set S which is to contain the nodes of a tree initially it is empty.
Step-3: Choose the least cost edge which starts from the element of the set S
which are not in the set S.
Step-4: Add the vertex to the tree, if it does not form a cycle and also add it to the set S.
Step-5: Repeat the steps 4 and 5 until (n-1) edges are selected.
 Implementation:

Let us consider the following graph with 6 vertices.

1. Initialize all the vertices with no edges.

2. Let the chosen vertex be A. so set S={A}.

3. The least among AB, AE, AF is AB. So S={A, B}.

4. The least among AE,AF,BC,BD,BE is BE. So set S={A, B, E}.

5. Remove the edge AE because it forms a cycle.

6. Least among the AF,BC,BD,ED is AF. So set S={A, B, E, F}
 7. The least among BD,BC,ED,FC,FD is FD. So set S={A,B,E,F,D}

8. The least among BD,BD,ED,FC is FC. So set S={A,B,E,F,D,C}.

Now, set contains all the vertices of the graph. So the process will stopped here. Therefore, the total
cost of minimum spanning tree is 2+1+4+4+3=14.

IMPORTANT QUESTOINS
1. What is searching? Explain different types of searching techniques?
2. What is linear searching? Explain with an example code?
3. What is binary searching? Explain with an example code?
4. What is Indexed linear searching? Explain with an example code?
5. What is sorting? Explain different types of sorting techniques?
6. Explain Bubble sort with example?
7. Explain Insertion sort with example?
8. Explain Merge sort with example?
9. What is a Graph? Explain its terminologies?
10. Explain the applications on graphs?
11. Explain the representation of Graphs?
12. Explain the graph traversal techniques?
13. Explain the Spanning Tree?

32