## Sorting – Bubble sort

**Bubble sort:
**Two consecutive elements are compared. It sorts the elements in right to left fashion. Thus, (n-i) comparisons are made.

**Example:**

**Frequency:**

i j number of times

———————————————————————————————

1 1 to n-i n-1

2 1 to n-i n-2

3 1 to n-i n-3

– – –

– – –

– – –

n-1 1 to n-(n-1) 1

Thus, 1+2+……………+(n-3)+(n-2)+(n-1)

which is sum of (n-1) terms.

=(n-1)(n-1+1)/2

=(n-1)n/2

=n^{2}/2 – n/2

=0.5n^{2}-0.5n

Thus, efficiency in Big(O) Notation is O(n^{2}).

**i)** **Best Case:** Data is already in sorted form. Thus no interchange occurs.

Number of comparisons may be reduced as follows:

for i=1, j=n-i ie. (n-1)

Frequency is (n-1), which is achieved if we quit after scan, when no interchange occurs.

Hence, efficiency is O(n).

**ii) Worst Case:** Data is in reverse order. Each value gets interchanged. Hence number of comparisons will be same as calculated above. i.e.

Efficiency = O(n^{2})

**iii) ****Average Case:**

(Best Case + Worst Case)/2

= ((n-1) + n^{2})/2

=(n/2)-(1/2)+(n^{2}/2)

Efficiency = O(n^{2})

**Bubble sort program with n ^{2} frequency and an efficiency of O(n^{2})**

#include <stdio.h>

#include <conio.h>

#define n 10

void main()

{

int arr[n], i,j,temp;

clrscr();

printf(“\nInitializing array…!”);

for(i=0;i<n;i++)

{

printf(“\nEnter elements?”);

scanf(“%d”,&arr[i]);

}

for(i=0;i<n-1;i++)

for(j=0;j<n-i-1;j++)

{

if(arr[j]>arr[j+1])

{

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

printf(“\nSorted array using Bubble sort is:\n”);

for(i=0;i<n;i++)

printf(“%d\t”,arr[i]);

getch();

}

**Bubble sort program with best efficiency O(n) and frequency (n-1)**

#include <stdio.h>

#include <conio.h>

#define n 5

void main()

{

int arr[n], i,j,temp,sort=0;

/*sort=0 for false and sort=1 for true i.e. sorted array*/

clrscr();

printf(“\nInitializing array…!”);

for(i=0;i<n;i++)

{

printf(“\nEnter elements?”);

scanf(“%d”,&arr[i]);

}

for(i=0;i<n-1 && sort!=1;i++)

{

for(j=0;j<n-i-1;j++)

{

sort=1;

if(arr[j]>arr[j+1])

{

sort=0;

temp=arr[j];

arr[j]=arr[j+1];

arr[j+1]=temp;

}

}

}

printf(“\nSorted array using Bubble sort is:\n”);

for(i=0;i<n;i++)

printf(“%d\t”,arr[i]);

getch();

}

## Sorting – Shell sort

**Shell Sort: **

Shell sort is quite similar to that of insertion sort with the only difference that in shell sort, higher values of k are considered. Whereas insertion sort assumes k to be 1. If k=4, then every 4^{th} element is compared, if it is 3 then every 3^{rd} element is compared. Thus k=m means every m^{th} element gets compared with each other and is swapped.

The value of k is decremented after each scan. The file is sorted, when k becomes 1 and swapping is performed for k = 1. The difference in original and decremented value(i.e. difference in k) may be generated using a hash function, which returns the number of decrements in k. say k=4, then k=2 and finally k=1. k=3 is skipped. or (k=8, k=4, k=2, k=1) or (k=4, k=3, k=2, k=1).

If k is taken as 1 only, then it is no more shell sort, it becomes insertion sort.

**Example:**

/*Program to implement Shell Sort*/

#include <stdio.h>

#include <conio.h>

#define MAX 5

void shellsort(int x[],int n,int incrmnts[],int numinc)

{

int incr,j,k,span,y;

for(incr=0;incr<numinc;incr++)

{

span=incrmnts[incr];

for(j=span;j<n;j++)

{

y=x[j];

for(k=j-span;k>=0 && y<x[k]; k-=span)

x[k+span]=x[k];

x[k+span]=y;

}

}

}

/*

A hash function may be defined as follows:

Let n be the size of the array (total number of elements).

Then begin from (n-3) upto 1.

Example: Let there are 8 elements, then n=8

increments array will hold 5,3,1 for (n-3), (n-5), (n-7) respectively.

and ct=3, where ct is numinc.

*/

int hash(int arr[],int n)

{

int i,j=0,ct=0;

for(i=3;(n-i)>0;i+=2)

{

arr[j++]=n-i;

ct++;

}

if(arr[j-1]!=1)

{arr[j]=1;

ct++;

}

return ct;

}

void main()

{

int arr[MAX],i,incrmnts[MAX], total_incr;

for(i=0;i<MAX;i++)

{

incrmnts[i]=0;

printf(“Enter value?”);

scanf(“%d”,&arr[i]);

}

total_incr = hash(incrmnts,MAX);

shellsort(arr,MAX,incrmnts,total_incr);

printf(“Sorted array is: “);

for(i=0;i<MAX;i++)

{

printf(“%d\t”,arr[i]);

}

getch();

}

## Indexed Sequential Search

**Indexed Sequential Search: **

In this searching technique, first of all an index file is created that contains references to a group of records, once an index is obtained, the partial searching takes less time since it is to be located in the group/bucket specified by the index. The program given below creates an index file for the employee records by grouping the records and then locates the required key by searching the index first and then returns the required record. The program to implement indexed sequential search is given below:

/*Indexed Sequential Search*/

#include <stdio.h>

#include <conio.h>

#define MAX 10

struct mainfile

{int empid;

char name[25];

float basic;

};

struct indexfile

{int index_id;

int kindex;

};

void main()

{

struct mainfile fobj[MAX];

struct indexfile index[MAX];

int i,num,low,high,ct=4;

float basicsal;

clrscr();

for(i=0;i<MAX;i++)

{

printf(“nEnter employee id?”);

scanf(“%d”,&fobj[i].empid);

printf(“nEnter name?”);

scanf(“%s”,fobj[i].name);

printf(“nEnter basic?”);

scanf(“%f”,&basicsal);

fobj[i].basic=basicsal;

}

printf(“nNow creating index file…!”);

for(i=0;i<(MAX/5);i++)

{index[i].index_id=fobj[ct].empid;

index[i].kindex = ct;

ct=ct+5;

}

printf(“nnEnter the empid to search?”);

scanf(“%d”,&num);

for(i=0;(i<MAX/5) && (index[i].index_id<=num);i++);

low=index[i-1].kindex;

high=index[i].kindex;

for(i=low;i<=high;i++)

{if(num==fobj[i].empid)

{

printf(“nThe record is: nt”);

printf(“nEmpid: %d”,fobj[i].empid);

printf(“nName: %s”,fobj[i].name);

printf(“nBasic: %f”,fobj[i].basic);

getch();

return;

}

}

printf(“nNumber not found…!”);

return;

}

## Hashing

**HASHING**

**Hashing:** It is an effective search technique used to locate an element with search key value or an index. We begin with a hash function that takes a key and maps it to some index in the array. If all the keys are mapped to different index then there is no problem. But, if several keys maps to the same index, a collision occurs which must be handled. Hashing provides a very fast access to records on search conditions. Hashing is used to provide a function called hash function, that is applied to a given key element to yield the address of the disk block in which it is to be stored.

Hashing may be either internal or external. Internal hashing applicable on internal files may be implemented as ranging from 0 to (n-1). We, then, chose a hash function that transforms the hash key field into an integer between 0 and (n-1). Hashing for disk files is called external hashing. Buckets (or memory location) are used to store more key elements. Each bucket contains one or more records. The hashing function maps a key into a relative bucket number. The collision chances are fewer since one or more key elements may be assigned to a bucket without any problem.

A hash function that maintains the records in the order of hash field values is called order preserving hash function. If the number of buckets/hash addresss space is fixed, the hashing technique is called static hashing. Thus, it is quite difficult to expand the table to accommodate more entries. In such a case, dynamic hashing schemes may be used that allow dynamic expansion and shrinking during run time. Extensible hashing is a dynamic hashing technique. In extensible hashing, additional buckets may be allocated dynamically as and when needed. Thus, the performance does not degrade with the increase in size.

**Hash Table:** The hash table or the lookup table contains two entries {key, index}. All the key indexes are initialized with zero. Hash table is used to store key elements such that the time taken for retrieval of any key is minimal as compared to other data structures, say linked list, stacks, queues, graphs etc. A hash function is required to hash/position the given key element in the hash table, such that locating that key element is almost instant provided we have defined an efficient hash function. The size of the hash table is predefined such that mapping of key elements to a hash table is done in the predefined limit. Hash function may consider the size of the hash table to generate the hash key to position the key element in the hash table. A hash function is considered to be good if it results in no or minimum collisions. Hashing may be used for indexing key elements or records to facilitate quick retrieval of data. A hash table contains a key value and an index, where index value specifies the state of the memory location i.e. whether it already contains a key element or is empty. Any flag may be used with values 0 or 1, where 0 indicates the position is empty and 1 indicates that it contains a key element. If a collision occurs i.e. more than one key value maps to the same index, collision resolution techniques are adopted for resolving collisions.

A hash function is considered to be an efficient hash function if it maps all or most of the keys to distinct locations.

Consider the following example:

25, 17, 19, 21, 18, 35, 38, 14

The hash function may be defined as follows:

int h(key)

{return (key%n);

}

where n is an integer, may be considered as 10. The hash table of size 10 for the above given integers may be defined as follows:

As per the given hash function, key element 35 should be inserted at index 5, but key index 5 is already 1 i.e. it occupies a valid key element, such a situation is called collision, which must be resolved. Similarly insertion of key 38 results in collision, since index 8 is already filled with 18 key value.

**Methods to Define Hash Functions:**

**Division Method****Truncation****Folding****Mid-Square Method****Multiplication Method****Radix Transformation****Digit Rearrangement**

**1. Division Method:** The given number is divided by an integer, that is usually considered to be the size of the hash table or lookup table. The remainder so obtained as a result of division is the hash key where this key element may be mapped in the table. Thus, if the hash table contains ten index entries from 0 to 9, the given integer may be divided by 10 to obtain the hash key for mapping that element in the hash table.

**2. ****Truncation:** Ignore a part of the key and use the remaining part directly as the index say for example, if a hash table contains 999 entries at the most or 999 different key indexes may be kept, then a hash function may be defined such that from an eight digit integer 12345678, first, second and fifth digits from the right may be used to define a key index i.e. 478, which is the key position in the hash lookup table where this element will be inserted. Any other key combination may be used.

**3. Folding:** Partition the key into several parts and combine the parts in a convenient way (often addition or multiplication) to obtain the index. Say for example an eight digit integer can be divided into groups of three, three and two digits (or any other combination) the groups added together and truncated if necessary to be in the proper range of indices. Hence 12345678 maps to 123+456+78 = 657, since any digit can affect the index, it offers a wide distribution of key values.

**4. Mid-Square Method:** In Mid-Square method, the key element is multiplied by itself to yield the square of the given key. If the hash table contains maximum 999 entries, then three digits from the result of square may be chosen as a hash key for mapping the key element in the lookup table. It generates random sequences of hash keys, which are generally key dependent. Mid Square method is a flexible method of selecting the hash key value.

**5. Multiplication Method:** For mapping a given key element in the hash table, individual digits of the key are multiplied. the result so obtained is divided by an integer, usually taken to be the size of the hash table to obtain the remainder as the hash key to place that element in the lookup table.

**6. Radix Transformation Method:** Where the value or key is digital, the number base (or radix) can be changed resulting in a different sequence of digits. For example: A decimal numbered key could be transformed into a hexadecimal numbered key. High order digits could be discarded to fit a hash value of uniform length.

**7. Digit Rearrangement:** This is simple taking part of the original value or key such as digits in position 3 through 6, reversing their order and then using that sequence of digits as the hash value or key.

**Collision Resolution:** If more than one key elements maps to the same index in the hash table, a collision is said to occur, and to resolve this collision, we may prefer using methods mentioned below:

- Linear Probing
- Quadratic Probing
- Random Probing
- Clustering
- Increment Functions/Rehashing/Double hashing
- Key Dependent Increments
- Collision Resolution by Chaining
- Coalesced Chaining

**Linear Probing:** If a collision occurs, we may perform a sequential search for the desired key or an empty location. Say for example: 14, 39, 11, 24

The hash function may be defined as-

int hash(int key)

{return (key%10);

** **}

This method searches for a vacant index in straight line from the mapped index that results in collision, hence it is called linear probing. The array may be considered circular for efficiency.

**Quadratic Probing:** If there is a collision at hash address h, this method probes the table at locations h+1, h+4, h+9…….. and so on i.e. at location h+i^{2}, for i=1,2,3………… i.e. the increment function is i^{2}.

**Random Probing:** A pseudorandom number generator may be used to obtain the increment. Thus a random number so generated defines the new index in the hash table to map a given key element such that the collision may be avoided.

**Clustering:** The Linear Probing method places the elements in a sequence, thus finding an empty location becomes time consuming as most of the key values get clustered together. If a few keys happen randomly to be near each other, then it becomes more and more likely that other keys will join them and the distribution will become progressively more unbalanced. Thus clustering occurs on account of placing elements in a sequence in case of collision, which must be avoided for proper arrangement of key elements in the hash table.

**Increment Functions:** To prevent clustering, re-hashing or double hashing may be used. If by using one hash function, collision occurs, then another hash function may be considered to obtain the result. (a vacant index in the hash table). This process of using another hash function to locate a new index in case of collision is called re-hashing or double hashing technique and is quite useful for arrangement of key elements at unique position.

**Key-dependent Increments:** We may truncate the key to a single digit and use it as an increment, say for the number 12345, the key may be defined as 123+45 i.e. 168 and if collision occurs at this index, then out of 12345, any digit say 5 may be used as an increment to the index i.e. 168+5=173 will be the new index, where the key may be placed in the hash table.

**Collision Resolution by Chaining:** It involves linking the key element at the end of the key element at the index where collision occurs. Thus, it may easily be implement by way of linked list where each index is a chain or linked list of various nodes combined together by means of address of the next node. An example given below illustrates the concept:

The following hash function may be considered:

int hash(int key)

{return (key/10);

}

For example: 45, 68, 15, 95, 86, 27, 55, 65, 84, 24, 59, 52

**A Chained Hash Table**

**Coalesced Chaining:** In this method, the key elements that take the same position in the hash table are linked together for easy retrieval and easy addition of new key elements. It is similar to linear probing, in which the keys mapped to the same hash address are placed at subsequent vacant address in the hash table, which are linked together in case of coalesced chaining. These links may be maintained via. storing address using pointers. When a new key element is to be inserted in a hash table, if an empty location is found, then the key is mapped at their address, otherwise the chain is traversed to locate next expty index for inserting the key element. This method of insertion of a key element in a hash table is termed as coalesced chaining.

**Ques.** Program to define a hash table/lookup table, which is used to retrieve values required by the user. Assume the numbers to be stored in the hash table to be of two digits, handled by this hash function for the sake of simplicity.

**Solution:**

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

#define MAX 10

void hash_table(int arr[][2],int num,int pos);

int hashfunc(int num);

void hash_table(int arr[][2],int num,int pos)

{if(arr[pos][1]==1)

{cout<<“Collision at index “<<pos;

exit(1);

}

arr[pos][0]=num;

arr[pos][1]=1;

}

int hashfunc(int num)

{return (num%10);

}

void main()

{

clrscr();

int hash[MAX][2],arr[MAX];

int i,j,pos;

for(i=0;i<MAX;i++)

hash[i][1]=0;

for(i=0;i<MAX;i++)

{cout<<“Enter value?”;

cin>>arr[i];

pos=hashfunc(arr[i]);

hash_table(hash,arr[i],pos);

}

int num;

cout<<“Enter the number you wish to search?”;

cin>>num;

pos=hashfunc(num);

if(hash[pos][1]==1)

{if(hash[pos][0]==num)

cout<<“Number found…!”<<hash[pos][0];

}

else

{cout<<“Number does not exist…!”;

}

getch();

}

**Symbol Tables:** A symbol table is merely a table with two fields, a name field and an information field. We need to be able to do the following jobs with a symbol table.

- determine whether a given name is in the table.
- add a new name to the table.
- access the information associated with a given name, and
- add new information for a given name.
- delete a name or group of name from the table.

The three symbol table mechanisms are linear list, trees and hash tables. We shall evaluate each scheme on the basis of the requirement to add n entries and make m inquiries.

- A linear list is the simplest scheme to implement, but the proformance becomes poor when m and n get large.
- A binary search tree gives better performance at some increase in implementation difficulty.
- Hashing schemes provide the best performance for somewhat greater programming effort and some extra space.

To implement a symbol table, the data structures used are linear lists, hash tables and various sorts of tree structures. A issue is the speed with which an entry can be added or accessed. A linear list is slow to access but simple to implement. A hash table is fast but more complex. Tree structures given intermediate performance.

**Symbol table structure:**

Data

Information

—————

Data Information

—-

—-

—-

—-

N

To appreciate the level of detail that goes into the symbol table contents, let us consider the data that can be associated with a name in the symbol. This information includes:

- The string of characters denoting the name.
- Attributes of the name(the attributes of a name determine its properties). The most important attribute of a name is its type, which determines what values it may have, possibly the way its value is to be represented in computer, and the operations to which it may be subjected. Other attributes of a name may determine its scope, that is, when its value is accessible.
- Parameters such as the number of dimensions of arrays and the upper and lower limits along each dimension.
- An offset describing the position in storage to be allocated for the same.

The structure of the symbol table may be declared as follows:

struct symboltable

{

char *name; /*name of the object*/

int size; /*size of name field*/

char type; /*data type*/

struct symboltable *next; /*address to next node*/

struct symboltable *link; /*address to next value*/

}symb;

Tables may be access tables implemented using arrays, triangular tables, jagged tables or hash tables.

## Graphs

**Graphs**

**Representation**- Adjacency Matrix
- Adjacency Lists

**Traversal schemes**- DFS (Depth First Search)
- Breadth First Search (BFS)

**Minimal Spanning**- Kruskal
- Prim

**Graph: **A graph consists of a set of nodes (vertices) and a set of arcs (or edges).

- The set of nodes {1,2,3,4}
- The set of arcs or edges {(1,2), (1,3), (1,4), (2,4), (2,3), (3,4)}

Thus a graph G consists of two sets V and E. V is a finite non-empty set of vertices. E is a set of pairs of vertices. These pairs are called edges. V(G) and E(G) will represent the sets of vertices and edges of graph G.

Thus, we may write G=(V,E) to represent a graph.

Tree |
Graph |

Root | No root |

Parent-child relationship | No such relationship |

Connected | May be disconnected |

acyclic |
May contain cycle |

(do not contain any cycle) |

**Directed Graphs:** If the pairs of nodes/vertices that make up the arcs are ordered pairs (direction of movement is used) the graph is said to be a directed graph (or digraph).

**NOTE:**

- The arrows between nodes represent arcs. The head of each arrow represents the second ndoe in the ordered pair of nodes making up an arc, and the tail of each arrow represents the first node in the pair.
- We use parenthesis to indicate an unordered pair and angular brackets to indicate an ordered pair.
- A graph need not be a tree but a tree must be a graph.
- Nodes need not have any arc associated with them.

**Incident Node: **A node n is incident to an arc x, if n is one of the two nodes in the ordered pair of nodes that constitute x. (We may also say that x is incident to n).

**Degree of a node:** The degree of a node is the number of arcs incident to it.

**Indegree:** The indegree of a node n is the number of arcs that have n as the head. (Arrows coming in n).

**Example:**

**Outdegree:** The outdegree of n is the number of arcs that have n as the tail. In the above graph, outdegree of 3 is 0 as it has no other node, for which it is a tail.

Outdegree of 2 is 2 i.e. {<2,1>, <2,3>}

**Note: **Maximum number of edges in any n vertex undirected graph is n(n-1)/2

**Complete Graph:** A n vertex undirected graph with exactly n(n-1)/2 edges is said to be a complete graph.

**Adjacent node:** A node n is adjacent to a node m if there is an arc from m to n. If n is adjacent to m, n is called a successor of m and m is called a predecessor of n.

**Weighted Graph or Network:** When a number is associated with each arc/edge i.e. edges have properties or attributes the graph is called a weighted graph or a network.

**Adjacency Matrix****Adjacency Lists**

**Connected Graph: **A graph is said to be connected if every pair of vertices in a graph is connected.

**Component of a graph:** A component of a graph is a maximal connected subgraph. In the above example there are two components.

**(i) Adjacency Matrix Representation:** A graph g with n vertices can be represented by a n*n matrix.

Since the above graph has 7 vertices, hence it can be represented by 7 X 7 matrix.

**Computing Degree of a Vertex:**

**(i) For an undirected graph:-** Degree is equal to sum of corresponding row = sum of corresponding column. For example: In the above table Degree of V2 = sum of row corresponding to V2 = sum of column corresponding to V2. (as shown by dotted lines), which is 2.

**(ii) For a directed graph:- **

Number of vertices = 4

Order of Adjacency Matrix = R x C = 4 x 4

**Note:**

- Sum of 1’s of the row gives outdegree.
- Sum of 1’s of the columns gives indegree.
- Sum of indegree + outdegree gives degree of that node

**Example:** In the above figure, Outdegree of V1 is 3 and Indegree of V1 is 0. Thus, Degree of V1 is 3+0=3.

**Adjacency Matrix for the above digraph is given below:**

**Finding total number of nodes:**

**(i) For an undirected graph: **To find the total number of edges of the graph, we find the sum of all 1’s except diagonal and divide it by 2 and add all 1’s of the diagonal.

**Example:**

Total number of edges = Sum of all 1’s except diagonal

= 8/2 = 4 + all 1’s of the diagonal ([ ]), which are all zero.

Thus, total number of edges = 4

**(ii) For a directed graph:** For a directed graph, total number of edges are given by sum of all 1’s.

**Example:**

Total number of edges = 5

**Implementation of Adjacency Matrix:**

**Example 1: **

Program to implement the above graph is as follows:

**Adjacency List:** We have an array of n elements (for a graph of n vertices). Each element has a linked list associated with it, which corresponds to the vertices, which are adjacent to the vertex.

**NOTE:
**

- Adjacent of node V1 is V2 and V3.
- Adjacent of node V2 is V1 and V4.
- Adjacent of node V3 is V1 and V4.
- Adjacent of node V4 is V2 and V3.

**For Graph G1:**

- Total number of edges in the graph = (Total number of nodes)/2 = 8/2 = 4 edges.
- Degree of a vertex can be found by counting the number of nodes for that particular value.

- Degree of vertex V1 = 2
- Degree of vertex V2 = 2
- Degree of vertex V3 = 2
- Degree of vertex V4 = 2

**For a directed graph:**

- Total number of edges in graph is equal to total number of nodes.
- Degree of a node is equal to number of nodes for that vertex.
- Outdegree of a vertex can be found out by simply counting the nodes of that element.

The indegree is calculated by traversing all the nodes and counting the occurrences of that vertex.

**NOTE:
**

- Adjacent of node V1 is V2, V3 and V4.
- Adjacent of node V2 is V3, V4 and V5.
- Adjacent of node V3 is V5.
- Adjacent of node V4 is V5.
- Adjacent of node V5 is V4.

**For Graph G2:**

- Total number of edges = Total number of nodes = 9
- Degree of a node = Number of nodes for that vertex

- Degree of V1 = 3
- Degree of V2 = 3
- Degree of V3 = 1
- Degree of V4 = 1
- Degree of V5 = 1

– Outdegree of a vertex = Number of nodes of that vertex.

- Outdegree of V1 is 3
- Outdegree of V2 is 3
- Outdegree of V3 is 1
- Outdegree of V4 is 1
- Outdegree of V5 is 1

– Indegree of a vertex = Traverse all nodes and count the occurrences of that vertex.

- Indegree of V1 = The occurrence of V1 is 0 (zero) i.e. no occurrence. Hence its indegree is zero.
- Indegree of V2 = 1 (since out of 9 nodes, it is visible only once).
- Indegree of V3 = 2
- Indegree of V4 = 3
- Indegree of V5 = 3

**Example:**

**Path Matrices of a given length:**Let us assume that a graph is completely described by its adjacency matrix, adj i.e. no data is associated with a graph. Consider the logical expression:

adj[i][k] and adj[k][j] are TRUE.

which means that there is an arc from i to node k and an arc from k to node j. Thus adj[i][k] && adj[k][j] equals TRUE if an only if there is a path of length 2 from i to j passing through k.

Consider an array adj2 such that adj2[i][j] is the value of the foregoing expression. adj2 is called the path matrix of length 2. adj[i][j] indicates whether or not there is a path of length 2 between i and j. Consider the following example:

The Adjacency Matrix for the above graph is shown below:

The path matrix for the above adjacency matrix is as follows:

**Traversal schemes:**

**DFS (Depth First Search)****BFS (Breadth First Search)**

**DFS (Depth First Search): **We move depth-wise i.e. we start from the first node (any of the vertex) and then visit the node that is adjacent to it. Then from that node we move to the vertex adjacent to it and so on. If we can’t move further, then return to the previous node and continue. We keep on marking the nodes which we have already visited.

**BFS (Breadth First Search):** After a node is visited, we first visit all the vertices adjacent to it.

**Example:** Refer to the above graph. BFS traversal result is-

V1, V2, V3, V4, V5, V6, V7, V8

**Spanning trees:** Spanning trees have two basic properties-

**(i) acyclic**

**(ii) connected**

If we define a subgraph of this graph, then all such possibilities that define it as a subgraph with no cycle may be referred to as spanning tree.

If the graph is a weighted graph, then it is often desired to create a spanning tree T for G such that the sum of weights of the tree edges in T is as small as possible. Such a tree is called a minimum spanning tree and represents the cheapest way of connecting all the nodes in G.

The dotted subgraph with least weight 60 is an example of minimum cost spanning tree, as it has minimum weight value.

There are a number of techniques for creating a minimum spanning tree for a weighted graph:

**Prim’s Algorithm****Kruskal’s algorithm****Round Robin Algorithm**

An arbitrary node is chosen initially as the tree root. The nodes of the graph are then appended to the tree one at a time until all nodes of the graph are included.

In figure (a), V1 is taken to be root of the tree, which is an arbitrary node chosen as a root. Adjacent of V1 is V2 and V3. V2 becomes the right child of V1 and V3 becomes the left child of V1 in the tree as shown in fig (b).

The nodes of the graph are initially considered as n distinct partial trees with one node each. At each step of the algorithm two distinct partial trees are connected into a single partial tree by an edge of the graph. When only one partial tree exists, it is a minimum spanning tree.

The issue is what connecting arc to use at each step. The answer is to use the arc of minimum cost that connects two distinct trees. To do this, the arcs can be placed in a priority queue based on weight. The arc of lowest weight is then examined to see if it connects two distinct trees.

An ascending order priority queue is constructed that contains the weights of the arcs of the given graphs as shown in the following figure:

Any further insertion is not required since number of vertices is equal to 4, which is the same as the total number of vertices in the given graph. Thus lower weights are chosen to construct minimum spanning tree.

**3. Round Robin Algorithm (given by Tarjan & Cheriton):**

It is similar to Kruskal’s algorithm except that there is a priority queue of arcs associated with each partial tree rather than one global priority queue of all un-examined arcs.

All partial trees are maintained in the queue, Q. Associated with each partial tree T, is a priority queue. P(T) of all arcs with exactly one incident node is the tree ordered by the weights of the arcs.

## Implementation of Adjacency List Representation for Graphs

**Graphs**

**Implementation of Adjacency List Representation for Graphs**

/*Implementation of Adjacency List Representation for graphs*/

#include <stdio.h>

#include <conio.h>

#include <string.h>

#include <stdlib.h>

#define MAX 4

struct edge;

typedef struct node

{

int id;

char city[25];

struct edge *next;

}VERTEX;

typedef struct edge

{

int adj;

int distance;

struct edge *next;

}EDGE;

VERTEX *nodes[MAX]={NULL};

VERTEX *makevertex(char str[],int pos)

{VERTEX *temp = (VERTEX *)malloc(sizeof(VERTEX));

temp->id = pos;

strcpy(temp->city,str);

temp->next=NULL;

return temp;

}

void getnode_info()

{

int i;

char city[25];

VERTEX *temp;

for(i=0;i<MAX;i++)

{printf(“Enter city name?”);

scanf(“%s”,city);

temp=makevertex(city,i);

nodes[i]=temp;

}

}

int return_subscript(char nm[])

{int i;

for(i=0;i<MAX;i++)

if(strcmp(nm,nodes[i]->city)==0)

return i;

return -1;

}

EDGE *makenode(int num,int j)

{

EDGE *temp = (EDGE *)malloc(sizeof(EDGE));

temp->adj=j;

temp->distance=num;

temp->next=NULL;

return temp;

}

VERTEX *join(VERTEX *node,EDGE *arc)

{VERTEX *temp=node;

EDGE *edg=temp->next;

if(node->next==NULL)

{node->next=arc;

return node;

}

while(edg->next!=NULL)

edg=edg->next;

temp->next=arc;

return node;

}

void display()

{int i;

EDGE *temp;

for(i=0;i<MAX;i++)

{printf(“%dt%st”,nodes[i]->id,nodes[i]->city);

temp=nodes[i]->next;

while(temp!=NULL)

{printf(“%d/%dt”,temp->adj,temp->distance);

temp=temp->next;

}

printf(“n”);

}

}

void main()

{

int ans,i,j;

EDGE *temp;

char city1[25],city2[25];

int distance;

getnode_info();

do

{

do

{printf(“nDoes route exists?”);

printf(“nFrom City?”);

scanf(“%s”,city1);

printf(“nTo City?”);

scanf(“%s”,city2);

i=return_subscript(city1);

j=return_subscript(city2);

}while(i==-1 || j==-1);

/*Now making node*/

printf(“nEnter distance?”);

scanf(“%d”,&distance);

temp=makenode(distance,j);

nodes[i]=join(nodes[i],temp);

printf(“nContinue(1/0)?”);

scanf(“%d”,&ans);

}while(ans==1);

display();

getch();

}

## Program to sketch a Graph using Adjacency matrix

**Graphs**

**Program to sketch a Graph using Adjacency matrix**

/*Program to sketch a graph using adjacency matrix*/

#include <stdio.h>

#include <conio.h>

#include <string.h>

#define MAX 4

struct vertex

{int num;

};

struct edge

{int adj;

};

struct graph

{struct vertex nodes[MAX];

struct edge edges[MAX][MAX];

}g;

int return_subscript(int val)

{int i;

for(i=0;i<MAX;i++)

{if(g.nodes[i].num==val)

return i;

}

return -1;

}

void display()

{

int i,j;

clrscr();

printf(“t”);

for(i=0;i<MAX;i++)

printf(“%dt”,g.nodes[i].num);

printf(“n”);

for(i=0;i<MAX;i++)

{printf(“%dt”,g.nodes[i].num);

for(j=0;j<MAX;j++)

printf(“%dt”,g.edges[i][j].adj);

printf(“n”);

}

}

void main()

{

int i,j,ans,n1,n2;

clrscr();

for(i=0;i<MAX;i++)

{printf(“nEnter vertex value?”);

scanf(“%d”,&g.nodes[i].num);

}

do

{

printf(“nEnter two nodes?”);

scanf(“%d %d”,&n1,&n2);

i=return_subscript(n1);

j=return_subscript(n2);

printf(“nDoes route exists(1/0)?”);

scanf(“%d”,&g.edges[i][j].adj);

printf(“nContinue(1/0)?”);

scanf(“%d”,&ans);

}while(ans==1);

do

{

printf(“nNow enter two nodes numbers?”);

printf(“nI will tell you whether route exists or not…”);

scanf(“%d %d”,&n1,&n2);

i=return_subscript(n1);

j=return_subscript(n2);

while(i==-1 || j==-1)

{printf(“nInvalid numbers! Try Again.”);

scanf(“%d %d”,&n1,&n2);

i=return_subscript(n1);

j=return_subscript(n2);

}

if(g.edges[i][j].adj==1)

printf(“nRoute exists…”);

else

printf(“nRoute does not exists…”);

printf(“nConfirm more entries(1/0)?”);

scanf(“%d”,&ans);

}while(ans==1);

display();

getch();

}

## Program to implement Graphs using Adjacency Matrix

**Graphs**

**Program to implement Graphs using Adjacency Matrix**

/*Implementation of adjacency matrix*/

#include <stdio.h>

#include <conio.h>

#include <string.h>

#define MAX 4

typedef struct node

{int id;

char city[25];

}VERTEX;

typedef struct edge

{int adj;

int distance;

}EDGE;

typedef struct graph

{VERTEX v[MAX];

EDGE e[MAX][MAX];

}GRAPH;

GRAPH g;

int return_subscript(char s[]);

void main()

{

int i,j;

char city1[25],city2[25];

int ans;

clrscr();

for(i=0;i<MAX;i++)

{printf(“nEnter City?”);

scanf(“%s”,g.v[i].city);

g.v[i].id = i;

}

printf(“nNow enter information about distance if a route exists!”);

do

{do

{

printf(“nEnter city1?”);

scanf(“%s”,city1);

printf(“nEnter city2?”);

scanf(“%s”,city2);

i=return_subscript(city1);

j=return_subscript(city2);

}while(i==-1 || j==-1);

printf(“nEnter distance?”);

g.e[i][j].adj=1;

scanf(“%d”,&g.e[i][j].distance);

printf(“More entries (1/0)?”);

scanf(“%d”,&ans);

}while(ans==1);

printf(“tt”);

for(i=0;i<MAX;i++)

printf(“%dt”,g.v[i].id);

printf(“ntt”);

for(i=0;i<MAX;i++)

printf(“%st”,g.v[i].city);

printf(“nn”);

for(i=0;i<MAX;i++)

{printf(“%d %st”,g.v[i].id,g.v[i].city);

for(j=0;j<MAX;j++)

printf(“%d/%dt”,g.e[i][j].adj,g.e[i][j].distance);

printf(“n”);

}

getch();

}

int return_subscript(char str[])

{int i;

for(i=0;i<MAX;i++)

if(strcmp(g.v[i].city,str)==0)

return i;

return -1;

}

## Program to implement MIN Priority Queue

**Priority Queue**

**Program to implement MIN Priority Queue**

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#define MAX 10

struct queue

{int front,rear;

int arr[MAX];

};

void push(struct queue *q,int x)

{

int f,r,i;

if(q->front==-1)

{q->arr[0]=x;

q->front=q->rear=0;

}

else

{

f=q->front;

r=q->rear;

while(f<=r && q->arr[f]<x)

f++;

for(i=r;i>=f;i–)

q->arr[i+1]=q->arr[i];

q->arr[f]=x;

q->rear++;

}

}

void display(struct queue *q)

{

int f,r;

for(f=q->front;f<=q->rear;f++)

{printf(“%dt”,q->arr[f]);

}

}

int pop(struct queue *q)

{

if(q->front==-1)

{printf(“Queue empty!”);

exit(1);

}

return(q->arr[q->front++]);

}

void main()

{

int ch,x;

struct queue q;

q.front=-1;

q.rear=-1;

while(1)

{

clrscr();

printf(“nMenun1. Pushn2. Popn3. Displayn4. Exit”);

printf(“nEnter your choice?”);

scanf(“%d”,&ch);

switch(ch)

{

case 1:

printf(“nEnter the number?”);

scanf(“%d”,&x);

push(&q,x);

break;

case 2:

x=pop(&q);

printf(“nPopped element is %d”,x);

break;

case 3:

display(&q);

break;

case 4:

exit(0);

default:

printf(“nInvalid choice!”);

}

getch();

}

}

## Program to implement MAX Priority Queue

**Priority Queues**

**Program to implement MAX Priority Queue**

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#define MAX 5

void display(struct queue *q);

struct queue

{int front,rear;

int arr[MAX];

};

void push(struct queue *q,int arr[],int n)

{

int i=0,j,f,r;

for(i=0;i<n;i++)

{if(q->front==-1)

{q->arr[0]=arr[i];

q->front=q->rear=0;

}

else

{f=q->front;

r=q->rear;

while(f<=r && q->arr[f]>arr[i])

f++;

for(j=r+1;j>=f;j–)

q->arr[j+1]=q->arr[j];

q->arr[f] = arr[i];

q->rear++;

}

}

}

void display(struct queue *q)

{

int f;

if(q->front==-1)

{printf(“nQueue is empty!”);

exit(1);

}

for(f=q->front;f<=q->rear;f++)

printf(“%dt”,q->arr[f]);

}

int pop(struct queue *q)

{if(q->front == -1)

{printf(“nQueue empty! Underflow.”);

return 0;

}

return (q->arr[q->front++]);

}

void main()

{

int arr[MAX],n,i,j,f;

struct queue q;

q.front = q.rear = -1;

clrscr();

printf(“nEnter total numbers?”);

scanf(“%d”,&n);

printf(“nEnter numbers?”);

for(i=0;i<n;i++)

scanf(“%d”,&arr[i]);

push(&q,arr,n);

printf(“nDisplaying elements of MAX Priority queue:”);

display(&q);

printf(“nPop an element from MAX Priority queue:”);

i=pop(&q);

printf(“nPopped element is maximum element i.e. %d”,i);

printf(“nMax Priority Queue after pop operation:”);

display(&q);

getch();

}