Scribd
Upload
2 views19 pages

C Programs for Prim's and Kruskal's Algorithms

The document outlines programming assignments for implementing Prim's and Kruskal's algorithms in C, as well as handling class imbalance using SMOTE and performing linear regression in Python. It includes objectives, theoretical explanations, algorithms, time and space complexities, and complete code implementations for each task. Additionally, it provides sample outputs and data handling techniques for the Python assignments.

Uploaded by

sushant.789.mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views19 pages

C Programs for Prim's and Kruskal's Algorithms

The document outlines programming assignments for implementing Prim's and Kruskal's algorithms in C, as well as handling class imbalance using SMOTE and performing linear regression in Python. It includes objectives, theoretical explanations, algorithms, time and space complexities, and complete code implementations for each task. Additionally, it provides sample outputs and data handling techniques for the Python assignments.

Uploaded by

sushant.789.mishra
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

Program 12:

Write a program in C to implement Prim’s Algorithm.

Objective: To implement Prim’s algorithm.

Theory: Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
weighted, connected, and undirected graph. It starts from any vertex and grows the MST by
continuously adding the smallest edge that connects a vertex in the tree to a vertex outside it. This
process repeats until all vertices are included. Prim’s algorithm ensures that the total weight of the
tree is minimal. Its time complexity is O(V²) for adjacency matrix and O(E log V) using a priority queue.

Algorithm: The Algorithm is given by:

Step 1: Start with a weighted connected graph.

Step 2: Choose any vertex as the starting vertex and add it to the MST set.

Step 3: Find the edge with the minimum weight that connects a vertex in the MST set to a vertex
outside the MST.

Step 4: Add that edge and the connected vertex to the MST set.

Step 5: Repeat Step 3 until all vertices are included in the MST.
Step 6: Display the edges and total minimum cost of the spanning tree.

Time and Space Complexity:

Time Complexity:

Time complexity is O(V²) for adjacency matrix and O(E log V) using a priority queue.

Space Complexity:

1-Using Adjacency Matrix:


Space Complexity = O(V²)
(since the matrix stores weights for all vertex pairs, even if no edge exists)

2-Using Adjacency List + Min Heap (Priority Queue):


Space Complexity = O(V + E)
(V for storing vertices and auxiliary arrays, E for storing edges)
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

C Program:

#include <stdio.h>

#include <limits.h>

#define V 5 // Number of vertices

int minKey(int key[], int mstSet[]) {

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (mstSet[v] == 0 && key[v] < min)

min = key[v], min_index = v;

return min_index; }

void printGraph(int graph[V][V]) {

printf(" Input Graph (Edges and Weights):\n");

for (int i = 0; i < V; i++) {

for (int j = i + 1; j < V; j++) {

if (graph[i][j] != 0)

printf(" %d -- %d (Weight: %d)\n", i, j, graph[i][j]); }}

printf("\n"); }

void printMST(int parent[], int graph[V][V]) {

int totalWeight = 0;

printf(" Edges in the Minimum Spanning Tree:\n");

printf(" Edge\tWeight\n");

for (int i = 1; i < V; i++) {

printf(" %d - %d\t%d\n", parent[i], i, graph[i][parent[i]]);

totalWeight += graph[i][parent[i]]; }

printf("\n Total Minimum Cost = %d\n\n", totalWeight); }

void printMSTVisual(int parent[], int graph[V][V]) {

printf(" Visual Representation of MST:\n");


Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

printf(" (root)\n");

printf(" 0\n");

for (int i = 1; i < V; i++) {

printf(" |\n");

printf(" └── %d (weight %d)\n", i, graph[i][parent[i]]); }

printf("\n"); }

void primMST(int graph[V][V]) {

int parent[V];

int key[V];

int mstSet[V];

for (int i = 0; i < V; i++)

key[i] = INT_MAX, mstSet[i] = 0;

key[0] = 0;

parent[0] = -1;

for (int count = 0; count < V - 1; count++) {

int u = minKey(key, mstSet);

mstSet[u] = 1;

for (int v = 0; v < V; v++)

if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])

parent[v] = u, key[v] = graph[u][v]; }

printMST(parent, graph);

printMSTVisual(parent, graph); }

int main() {

int graph[V][V] = {

{0, 2, 0, 6, 0},

{2, 0, 3, 8, 5},

{0, 3, 0, 0, 7},
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

{6, 8, 0, 0, 9},

{0, 5, 7, 9, 0} };

printGraph(graph);

primMST(graph);

return 0; }
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

Program 13:

Write a C program to implement Kruskal’s Algorithm.

Objective: To implement Kruskal’s Algorithm.

Theory: Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, weighted, and undirected graph. It works by sorting all edges in non-decreasing order of
their weights, then repeatedly adding the smallest edge to the MST if it doesn’t form a cycle (checked
using the Disjoint Set/Union-Find method). This continues until all vertices are connected.

Algorithm: The Algorithm is given by:

Step 1: Sort all edges in ascending order of their weights.

Step 2: Initialize each vertex as a separate set (Disjoint Sets).

Step 3: Pick the smallest edge.

Step 4: If adding this edge doesn’t form a cycle, include it in the MST.

Step 5: Repeat until the MST contains V – 1 edges.

Step 6: Display all MST edges and total cost.

Time and Space Complexity:

Time Complexity:

time complexity is O(E log E)

Space Complexity:

space complexity is O(V + E).

C Program:

#include <stdio.h>

#include <stdlib.h>

#define V 5

#define E 7 // Number of edges in the graph

struct Edge {
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

int src, dest, weight; };

struct Subset {

int parent, rank; };

int find(struct Subset subsets[], int i) {

if (subsets[i].parent != i)

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent; }

void Union(struct Subset subsets[], int x, int y) {

int xroot = find(subsets, x);

int yroot = find(subsets, y);

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

else {

subsets[yroot].parent = xroot;

subsets[xroot].rank++; } }

int compare(const void *a, const void *b) {

struct Edge *a1 = (struct Edge *)a;

struct Edge *b1 = (struct Edge *)b;

return a1->weight > b1->weight; }

void KruskalMST(struct Edge edges[]) {

struct Edge result[V]; // Stores the resultant MST

int e = 0; // Index for result[]

int i = 0; // Index for sorted edges

int totalWeight = 0;

qsort(edges, E, sizeof(edges[0]), compare);


Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

struct Subset *subsets = (struct Subset *)malloc(V * sizeof(struct Subset));

for (int v = 0; v < V; ++v) {

subsets[v].parent = v;

subsets[v].rank = 0;

printf(" Input Graph (Edges and Weights):\n");

for (int k = 0; k < E; k++)

printf(" %d -- %d (Weight: %d)\n", edges[k].src, edges[k].dest, edges[k].weight);

printf("\n");

while (e < V - 1 && i < E) {

struct Edge next_edge = edges[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

if (x != y) {

result[e++] = next_edge;

Union(subsets, x, y); }}

printf(" Edges in the Minimum Spanning Tree:\n");

printf(" Edge\tWeight\n");

for (i = 0; i < e; ++i) {

printf(" %d - %d\t%d\n", result[i].src, result[i].dest, result[i].weight);

totalWeight += result[i].weight; }

printf("\n Total Minimum Cost = %d\n\n", totalWeight);

printf(" └── %d (weight %d)\n", result[i].dest, result[i].weight); }

free(subsets); }

int main() {

struct Edge edges[E] = {


Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAA lab Subject Code: BCS-553 Semester: V

{0, 1, 2},

{0, 3, 6},

{1, 2, 3},

{1, 3, 8},

{1, 4, 5},

{2, 4, 7},

{3, 4, 9} };

KruskalMST(edges);

return 0; }
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Program 9:

Write a Python Program to find and handle the imbalance of classification in given dataset (using
smote function)

import pandas as pd

import numpy as np

import [Link] as plt

import seaborn as sns

Code:

df=pd.read_csv("/content/[Link]")

Code:

[Link](5)

Code:

[Link]()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code:

[Link]().sum()

Code:

[Link]().sum()

Output: np.int64(0)

Code:

df['Outcome'].value_counts()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code: X=[Link]('Outcome',axis=1)

X
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code:

[Link]

Outcome: (768, 8)

Code:

Y=df[['Outcome']]

Outcome:

Code:

from imblearn.over_sampling import SMOTE

sm=SMOTE()

xmod, ymod = sm.fit_resample(X, Y)

xmod
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Ymod

ymod.value_counts()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Program 10:

Write a Python Program to perform linear regression modelling on the given dataset and predict the
new query on this model.

import pandas as pd

import numpy as np

import [Link] as plt

import seaborn as sns

Code:

df=pd.read_csv("/content/[Link]")

Code:

[Link](5)

Code:

[Link]()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code:

[Link]().sum()

Code:

[Link]().sum()

Output: np.int64(0)

Code:

df['Outcome'].value_counts()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code: X=[Link]('Outcome',axis=1)

X
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code:

[Link]

Outcome: (768, 8)

Code:

Y=df[['Outcome']]

Outcome:

Code:

from imblearn.over_sampling import SMOTE

sm=SMOTE()

xmod, ymod = sm.fit_resample(X, Y)

xmod
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Ymod

ymod.value_counts()
Ajay Kumar Garg Engineering College, Ghaziabad

Name: Sushant Mishra Roll Number:2300271540128

Subject: DAV lab Subject Code: BCDS-551 Semester: V

Code:

from sklearn.linear_model import LogisticRegression

LCR= LogisticRegression()

[Link](xmod, ymod)

Code:

[Link]([[2,117,62,23,94,42,0.196, 50]])

You might also like