1.Assume that a project of road construction to connect some cities is given to your friend.
Map of these
cities and roads which will connect them (after construction) is provided to him in the form of a graph.
Certain amount of rupees is associated with construction of each road. Your friend has to calculate the
minimum budget required for this project. The budget should be designed in such a way that the cost of
connecting the cities should be minimum and number of roads required to connect all the cities should be
minimum (if there are N cities then only N-1 roads need to be constructed). He asks you for help. Now, you
have to help your friend by designing an algorithm which will find minimum cost required to connect these
cities. (use Prim's algorithm)
#include <stdio.h>
#include <stdlib.h>
int** createMatrix(int V);
int find_min_edge(int included[], int *keys, int V);
void print(int parent[], int V, int **G);
void prim(int V, int **G);
int main() {
int V;
printf("Enter the number of vertices: ");
scanf("%d", &V);
int **G = createMatrix(V);
printf("Enter the adjacency matrix:\n");
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
scanf("%d", &G[i][j]);
prim(V, G);
for(int i = 0; i < V; i++)
free(G[i]);
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
free(G);
return 0;
}
int** createMatrix(int V) {
int** mat = (int**)malloc(V * sizeof(int*));
for (int i = 0; i < V; i++) {
mat[i] = (int*)malloc(V * sizeof(int));
}
return mat;
}
int find_min_edge(int included[], int *keys, int V) {
int min = 1000, min_index;
for (int v = 0; v < V; v++)
if (included[v] == 0 && keys[v] < min)
min = keys[v], min_index = v;
return min_index;
}
void print(int parent[], int V, int **G) {
int total_weight = 0;
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++) {
printf("%d - %d \t%d \n", parent[i], i, G[i][parent[i]]);
total_weight += G[i][parent[i]];
}
printf("Minimum Spanning Weight: %d", total_weight);
}
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
void prim(int V, int **G) {
int parent[V];
int included[V];
int keys[V];
for (int i = 0; i < V; i++)
keys[i] = 1000, included[i] = 0;
parent[0] = -1;
keys[0] = 0;
for (int count = 0; count < V - 1; count++) {
int u = find_min_edge(included, keys, V);
included[u] = 1;
for (int v = 0; v < V; v++)
if (G[u][v] && included[v] == 0 && G[u][v] < keys[v])
parent[v] = u, keys[v] = G[u][v];
}
print(parent, V, G);
}
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
OUTPUT
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
2. Assume that a project of road construction to connect some cities is given to your friend. Map of these
cities and roads which will connect them (after construction) is provided to him in the form of a graph.
Certain amount of rupees is associated with construction of each road. Your friend has to calculate the
minimum budget required for this project. The budget should be designed in such a way that the cost of
connecting the cities should be minimum and number of roads required to connect all the cities should be
minimum (if there are N cities then only N-1 roads need to be constructed). He asks you for help. Now, you
have to help your friend by designing an algorithm which will find minimum cost required to connect these
cities. Implement the problem using Kruskal's algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
typedef struct{
int src, dest, weight;
}Edge;
typedef struct{
int vertices, edges;
Edge* edge;
}Graph;
Graph* createGraph(int vertices, int edges);
int find(int parent[], int i);
void Union(int parent[], int x, int y);
int myComp(const void* a, const void* b);
void Kruskal(Graph* graph, int V);
int main(){
int V, E;
printf("Enter the number of vertices and edges:\n");
scanf("%d %d", &V, &E);
Graph* graph = createGraph(V, E);
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
printf("Enter source vertex, destination vertex and weight of each edge:\n");
for(int i=0; i<E; i++){
scanf("%d %d %d", &graph->edge[i].src, &graph->edge[i].dest, &graph->edge[i].weight);
}
Kruskal(graph, V);
return 0;
}
Graph* createGraph(int vertices, int edges){
Graph* graph = (Graph*) malloc(sizeof(Graph));
graph->vertices = vertices;
graph->edges = edges;
graph->edge = (Edge*) malloc(graph->edges * sizeof(Edge));
return graph;
}
int find(int parent[], int i){
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void Union(int parent[], int x, int y){
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
int myComp(const void* a, const void* b){
Edge* a1 = (Edge*)a;
Edge* b1 = (Edge*)b;
return a1->weight > b1->weight;
}
void Kruskal(Graph* graph, int V){
int e = 0;
int i = 0;
Edge result[V];
qsort(graph->edge, graph->edges, sizeof(graph->edge[0]), myComp);
int *parent = (int*) malloc(V * sizeof(int));
memset(parent, -1, sizeof(int) * V);
while (e < V - 1 && i < graph->edges){
Edge next_edge = graph->edge[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y){
result[e++] = next_edge;
Union(parent, x, y);
}
}
printf("Following are the edges in the constructed MST\n");
int minimumCost = 0;
for (i = 0; i < e; ++i){
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
minimumCost += result[i].weight;
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
}
printf("Minimum Cost Spanning Tree: %d", minimumCost);
}
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
OUTPUT
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
3. Assume that same road construction project is given to another person. The amount he will earn from
this project is directly proportional to the budget of the project. This person is greedy, so he decided to
maximize the budget by constructing those roads who have highest construction cost. Design an algorithm
and implement it using a program to find the maximum budget required for the project.
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int src, dest, weight;
} Edge;
int compare(const void* a, const void* b) {
return ((Edge*)b)->weight - ((Edge*)a)->weight;
}
int find(int parent[], int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void Union(int parent[], int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
if(xset!=yset)
parent[xset] = yset;
}
void MaximumSpanningTree(Edge* edges, int V, int E) {
qsort(edges, E, sizeof(Edge), compare);
int* parent = (int*)malloc(V * sizeof(int));
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
for (int v = 0; v < V; ++v)
parent[v] = -1;
int total_weight = 0;
for (int i = 0; i < E; ++i) {
int x = find(parent, edges[i].src);
int y = find(parent, edges[i].dest);
if (x != y) {
total_weight += edges[i].weight;
Union(parent, x, y);
}
}
printf("Maximum Spanning Weight: %d\n", total_weight);
}
int main() {
int V;
printf("Enter number of vertices: ");
scanf("%d", &V);
int E = V * (V - 1) / 2;
Edge* edges = (Edge*)malloc(E * sizeof(Edge));
int k = 0;
printf("Enter the adjacency matrix:\n");
for(int i = 0; i < V; i++){
for(int j = 0; j < V; j++){
int weight;
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
scanf("%d", &weight);
if(i < j){
edges[k].src = i;
edges[k].dest = j;
edges[k].weight = weight;
k++;
}
}
}
MaximumSpanningTree(edges, V, E);
free(edges);
return 0;
}
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
OUTPUT
Nimisha Verma Section:B Class Rno.:43 University Rno.:2018964
