2020 350 047
Jamia Hamdard
Department of Computer Science & Engineering
School of Engineering Science &Technology
New Delhi - 110062
Design and Analysis of Algorithm
Btech CSE AI
2nd Year, 4rth Sem
Submitted by : Submitted to :
Nadir Johar Ms Anam Saiyeda
2020 350 047
2020 350 047
INDEX
[Link] TOPIC SIGN
1 Quick sort
2 Merge sort
3 Selection sort
4 Insertion sort
5 Bubble sort
6 Heap sort
7 Strassen’s matrix multiplication
8 Fractional knapsack
9 Huffman coding
10 Kruskal’s algorithm
11 Prim’s algorithm
12 Dijkstra’s algorithm
13 DFS
14 BFS
2020 350 047
Q. Find Minimum Cost Spanning Tree of a given
undirected graph using Kruskal's algorithm.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);
void main()
printf("\n\tImplementation of Kruskal's Algorithm\n");
printf("\nEnter the no. of vertices:");
scanf("%d",&n);
printf("\nEnter the cost adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
printf("The edges of Minimum Cost Spanning Tree are\n");
while(ne < n)
{
2020 350 047
for(i=1,min=999;i<=n;i++)
for(j=1;j <= n;j++)
if(cost[i][j] < min)
min=cost[i][j];
a=u=i;
b=v=j;
u=find(u);
v=find(v);
if(uni(u,v))
printf("%d edge (%d,%d) =%d\n",ne++,a,b,min);
mincost +=min;
cost[a][b]=cost[b][a]=999;
printf("\n\tMinimum cost = %d\n",mincost);
getch();
int find(int i)
while(parent[i])
i=parent[i];
return i;
int uni(int i,int j)
{
2020 350 047
if(i!=j)
parent[j]=i;
return 1;
return 0;
}
2020 350 047
Q. Find Minimum Cost Spanning Tree of a given
undirected graph using Prim’s algorithm.
#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];
void main()
printf("\nEnter the number of nodes:");
scanf("%d",&n);
printf("\nEnter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&cost[i][j]);
if(cost[i][j]==0)
cost[i][j]=999;
}
2020 350 047
visited[1]=1;
printf("\n");
while(ne < n)
for(i=1,min=999;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]< min)
if(visited[i]!=0)
min=cost[i][j];
a=u=i;
b=v=j;
if(visited[u]==0 || visited[v]==0)
printf("\n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
mincost+=min;
visited[b]=1;
cost[a][b]=cost[b][a]=999;
}
2020 350 047
2020 350 047
Q. From a given vertex in a weighted connected
graph, find shortest paths to other vertices using
Dijkstra's algorithm.
#include <stdio.h>
#define INFINITY 9999
#define MAX 10
void Dijkstra(int Graph[MAX][MAX], int n, int start);
void Dijkstra(int Graph[MAX][MAX], int n, int start)
int cost[MAX][MAX], distance[MAX], pred[MAX];
int visited[MAX], count, mindistance, nextnode, i, j;
// Creating cost matrix
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (Graph[i][j] == 0)
cost[i][j] = INFINITY;
else
cost[i][j] = Graph[i][j];
for (i = 0; i < n; i++)
distance[i] = cost[start][i];
pred[i] = start;
visited[i] = 0;
}
2020 350 047
distance[start] = 0;
visited[start] = 1;
count = 1;
while (count < n - 1)
mindistance = INFINITY;
for (i = 0; i < n; i++)
if (distance[i] < mindistance && !visited[i])
mindistance = distance[i];
nextnode = i;
visited[nextnode] = 1;
for (i = 0; i < n; i++)
if (!visited[i])
if (mindistance + cost[nextnode][i] < distance[i]) {
distance[i] = mindistance + cost[nextnode][i];
pred[i] = nextnode;
count++;
// Printing the distance
for (i = 0; i < n; i++)
if (i != start) {
2020 350 047
printf("\nDistance from source to %d: %d", i, distance[i]);
int main()
int Graph[MAX][MAX], i, j, n, u;
n = 7;
Graph[0][0] = 0;
Graph[0][1] = 0;
Graph[0][2] = 1;
Graph[0][3] = 2;
Graph[0][4] = 0;
Graph[0][5] = 0;
Graph[0][6] = 0;
Graph[1][0] = 0;
Graph[1][1] = 0;
Graph[1][2] = 2;
Graph[1][3] = 0;
Graph[1][4] = 0;
Graph[1][5] = 3;
Graph[1][6] = 0;
Graph[2][0] = 1;
Graph[2][1] = 2;
Graph[2][2] = 0;
Graph[2][3] = 1;
2020 350 047
Graph[2][4] = 3;
Graph[2][5] = 0;
Graph[2][6] = 0;
Graph[3][0] = 2;
Graph[3][1] = 0;
Graph[3][2] = 1;
Graph[3][3] = 0;
Graph[3][4] = 0;
Graph[3][5] = 0;
Graph[3][6] = 1;
Graph[4][0] = 0;
Graph[4][1] = 0;
Graph[4][2] = 3;
Graph[4][3] = 0;
Graph[4][4] = 0;
Graph[4][5] = 2;
Graph[4][6] = 0;
Graph[5][0] = 0;
Graph[5][1] = 3;
Graph[5][2] = 0;
Graph[5][3] = 0;
Graph[5][4] = 2;
Graph[5][5] = 0;
Graph[5][6] = 1;
2020 350 047
Graph[6][0] = 0;
Graph[6][1] = 0;
Graph[6][2] = 0;
Graph[6][3] = 1;
Graph[6][4] = 0;
Graph[6][5] = 1;
Graph[6][6] = 0;
u = 0;
Dijkstra(Graph, n, u);
return 0;
}
2020 350 047
2020 350 047
Q. Check whether a given graph is connected or
not using DFS
method.
#include<stdio.h>
#include<conio.h>
int a[20][20],reach[20],n;
void dfs(int v)
int i;
reach[v]=1;
for(i=1;i<=n;i++)
if(a[v][i] && !reach[i])
printf("\n %d->%d",v,i);
dfs(i);
void main()
int i,j,count=0;
printf("\n Enter number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
reach[i]=0;
for(j=1;j<=n;j++)
a[i][j]=0;
}
2020 350 047
printf("\n Enter the adjacency matrix:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
dfs(1);
printf("\n");
for(i=1;i<=n;i++)
if(reach[i])
count++;
if(count==n)
printf("\n Graph is connected");
else
printf("\n Graph is not connected");
getch();
}
2020 350 047
2020 350 047
Q. Print all the nodes reachable from a given
starting node in a
digraph using BFS method.
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
for(i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
visited[q[f]]=1;
bfs(q[f++]);
void main()
int v;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for(i=1;i<=n;i++)
q[i]=0;
visited[i]=0;
}
2020 350 047
printf("\n Enter graph data in matrix form:\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for(i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
getch();
}
2020 350 047