Scribd
Upload
21 views

DSC314 Data Structure Lab4

Uploaded by

Daksh Dheer
Copyright
© © All Rights Reserved
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
21 views

DSC314 Data Structure Lab4

Uploaded by

Daksh Dheer
Copyright
© © All Rights Reserved
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
You are on page 1/ 10

14. C program for Prim's Minimum Spanning Tree (MST) algorithm.

The program is
for adjacency matrix representation of the graph

We start from one vertex and keep adding edges with the lowest weight until we reach our goal.
The steps for implementing Prim's algorithm are as follows:

1.Initialize the minimum spanning tree with a vertex chosen at random.

2.Find all the edges that connect the tree to new vertices, find the minimum and add it to the tree

3.Keep repeating step 2 until we get a minimum spanning tree


#include <stdio.h>
#include <stdbool.h>

#define INF 9999999


#define V 5 // Number of vertices in the graph

// Function to print the MST


void printMST(int graph[V][V], int selected[]);

int main() {
// Adjacency matrix for the graph
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}
};

int selected[V] = {0}; // Track selected vertices


int no_edge = 0; // Count of edges in MST

// Select the first vertex


selected[0] = true;

// Print the heading


printf("Edge : Weight\n");

// Loop until we have V-1 edges in the MST


while (no_edge < V - 1) {
int minimum = INF;
int x = 0, y = 0;

// Find the smallest edge from the set of selected vertices


for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j] && G[i][j] < minimum) {
minimum = G[i][j];
x = i;
y = j;
}
}
}
}

// Print the edge and weight


printf("%d - %d : %d\n", x, y, G[x][y]);

// Select the vertex


selected[y] = true;

// Increment the number of edges


no_edge++;
}

return 0;
}
15.// C program to implement a stack using singly linked list

#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;

void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
void push ()
{
int val;
struct node *ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");

}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d",ptr->val);
ptr = ptr->next;
if (ptr!=NULL)
printf(" -> ");
}
}
}
}
16.// C program to implement the queue data structure using
// linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *back;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{
printf("\n*************************Main Menu*****************************\n");
printf("n=========================================================\n");
printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
struct node *ptr;
int item;

ptr = (struct node *) malloc (sizeof(struct node));


if(ptr == NULL)
{
printf("\nOVERFLOW\n");
return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
back = ptr;
front -> next = NULL;
back -> next = NULL;
}
else
{
back -> next = ptr;
back = ptr;
back->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf(" %d ",ptr -> data);
ptr = ptr -> next;
if(ptr != NULL)
printf("->");
}
}
}

You might also like