Scribd
Upload
5 views

Lab2

The document describes two algorithms for finding the Minimum Spanning Tree (MST) of a graph: Prim's and Kruskal's algorithms. Prim's algorithm grows the MST from an arbitrary vertex by selecting the smallest edge, while Kruskal's algorithm adds edges in increasing order of weight, ensuring no cycles are formed. Each algorithm includes a detailed explanation, pseudocode, and characteristics such as time and space complexity.

Uploaded by

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

Lab2

The document describes two algorithms for finding the Minimum Spanning Tree (MST) of a graph: Prim's and Kruskal's algorithms. Prim's algorithm grows the MST from an arbitrary vertex by selecting the smallest edge, while Kruskal's algorithm adds edges in increasing order of weight, ensuring no cycles are formed. Each algorithm includes a detailed explanation, pseudocode, and characteristics such as time and space complexity.

Uploaded by

DEVRAJ SILWAL
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

Lab – 16

Title: WAP to find the minimum spanning tree using Prim’s Algorithm.
Theory:
Prim's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a
connected, weighted, and undirected graph. The MST connects all vertices of the graph while
minimizing the total edge weight. The algorithm starts with an arbitrary vertex and grows the
MST by selecting the smallest edge that connects a vertex in the MST to a vertex outside it.
Algorithm:
Step 1: Initialize a set of vertices that are included in the MST.
Step 2: Choose an arbitrary vertex and set its key value to 0.
Step 3: Select the vertex with the smallest key value that is not yet included in the MST.
Step 4: Update the key values of the adjacent vertices.
Step 5: Repeat steps 3 and 4 until all vertices are included in the MST.
Step 6: Return the MST edges and the total weight.

Characteristics:
 Time Complexity: O(V^2), where V is the number of vertices (for a simple
implementation without priority queues).
 Space Complexity: O(V), for storing the MST and key values of vertices.
Source Code:
#include <stdio.h>
#include <limits.h>
#define MAX 30

int Graph[MAX][MAX], parent[MAX], n;

void primsAlgo()
{
int cost = 0;
int key[MAX], mstSet[MAX];
for (int i = 0; i < n; i++)
{
key[i] = INT_MAX;
mstSet[i] = 0;
}

key[0] = 0;
parent[0] = -1;

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


{
int u = -1, min = INT_MAX;
for (int v = 0; v < n; v++)
{
if (!mstSet[v] && key[v] < min)
{
min = key[v];
u = v;
}
}

mstSet[u] = 1;

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


{
if (Graph[u][v] && !mstSet[v] && Graph[u][v] < key[v])
{
key[v] = Graph[u][v];
parent[v] = u;
}
}
}

printf("\t--------------------------\n");
printf("\tPrim's Algorithm\n");
printf("\t--------------------------\n");
printf("Edges in the Minimum Spanning Tree (MST):\n");
for (int i = 1; i < n; i++)
{
printf("%d - %d : %d\n", parent[i], i, Graph[i][parent[i]]);
cost += Graph[i][parent[i]];
}

printf("Total cost of the MST: %d\n", cost);


}

int main()
{
n = 5;
int G[MAX][MAX] = {
{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}
};

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


{
for (int j = 0; j < n; j++)
{
Graph[i][j] = G[i][j];
}
}

primsAlgo();

printf("\n\nCompiled By: DEVRAJ SILWAL\n");


return 0;
}
Output:
Lab – 15
Title: WAP to find the minimum spanning tree using Kruskal’s Algorithm.
Theory:
Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST)
of a connected, undirected, and weighted graph. The MST connects all vertices of the graph
with the minimum total edge weight. Unlike Prim's algorithm, Kruskal’s algorithm starts
with the edges and works by adding edges in increasing order of weight, ensuring no cycle is
formed.
Algorithm:
Step 1: Sort all edges in the graph by their weight in ascending order.

Step 2: Initialize a disjoint-set (or union-find) data structure to keep track of the connected
components.

Step 3: Pick the smallest edge from the sorted edges list. Check if it forms a cycle by
checking if the two vertices of the edge belong to the same set.

Step 4: If it does not form a cycle, add the edge to the MST and union the two sets of the
two vertices.

Step 5: Repeat step 3 and 4 until there are V-1 edges in the MST (where V is the number
of vertices).

Step 6: Return the MST edges and the total weight.

Characteristics:
 Time Complexity: O(E log E), where E is the number of edges.
 Space Complexity: O(V + E) ,where V is the number of nodes.
Source Code:
#include <stdio.h>
#define MAX 30

struct Edge {
int u, v, w;
};

int Graph[MAX][MAX], parent[MAX], n;


struct Edge edges[MAX], mst[MAX];

void kruskalAlgo()
{
int i, j, count = 0, mstEdges = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < i; j++)
{
if (Graph[i][j] != 0)
{
edges[count++] = (struct Edge){i, j, Graph[i][j]};
}
}
}
for (i = 0; i < count - 1; i++)
{
for (j = 0; j < count - i - 1; j++)
{
if (edges[j].w > edges[j + 1].w)
{
struct Edge temp = edges[j];
edges[j] = edges[j + 1];
edges[j + 1] = temp;
}
}
}
for (i = 0; i < n; i++)
parent[i] = i;

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


{
int u = edges[i].u, v = edges[i].v;
int rootU = u, rootV = v;
while (parent[rootU] != rootU)
rootU = parent[rootU];

while (parent[rootV] != rootV)


rootV = parent[rootV];

if (rootU != rootV)
{
mst[mstEdges++] = edges[i];
parent[rootV] = rootU;
}
}
int cost = 0;
printf("\t--------------------------\n");
printf("\tKruskal's Algorithm\n");
printf("\t--------------------------\n");

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


for (i = 0; i < mstEdges; i++)
{
printf("%d - %d : %d\n", mst[i].u, mst[i].v, mst[i].w);
cost += mst[i].w;
}

printf("Total cost of the MST: %d\n", cost);


}

int main()
{
n = 5;
int G[MAX][MAX] = {
{0, 7, 0, 5, 0},
{7, 0, 8, 9, 7},
{0, 8, 0, 7, 5},
{5, 9, 7, 0, 6},
{0, 7, 5, 6, 0}
};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
Graph[i][j] = G[i][j];
}
kruskalAlgo();
printf("\n\nCompiled By: DEVRAJ SILWAL\n");
return 0;
}
Output:

You might also like