Untitled

From chenqin, 3 Years ago, written in Plain Text.

Embed

Download Paste or View Raw
Hits: 100

Minimum Spanning Tree using Prim's Algorithm :-

// A C / C++ program for Prim's Minimum

// Spanning Tree (MST) algorithm. The program is

// for adjacency matrix representation of the graph

#include <stdio.h>

#include <limits.h>

#include<stdbool.h>

// Number of vertices in the graph

#define V 5

// A utility function to find the vertex with

// minimum key value, from the set of vertices

// not yet included in MST

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

{

// Initialize min value

int min = INT_MAX, min_index;

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

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

min = key[v], min_index = v;

return min_index;

}

// A utility function to print the

// constructed MST stored in parent[]

int printMST(int parent[], int n, int graph[V][V])

{

printf("Edge \tWeight\n");

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

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

}

// Function to construct and print MST for

// a graph represented using adjacency

// matrix representation

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

{

// Array to store constructed MST

int parent[V];

// Key values used to pick minimum weight edge in cut

int key[V];

// To represent set of vertices not yet included in MST

bool mstSet[V];

// Initialize all keys as INFINITE

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

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

// Always include first 1st vertex in MST.

// Make key 0 so that this vertex is picked as first vertex.

key[0] = 0;

parent[0] = -1; // First node is always root of MST

// The MST will have V vertices

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

{

// Pick the minimum key vertex from the

// set of vertices not yet included in MST

int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set

mstSet[u] = true;

// Update key value and parent index of

// the adjacent vertices of the picked vertex.

// Consider only those vertices which are not

// yet included in MST

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

// graph[u][v] is non zero only for adjacent vertices of m

// mstSet[v] is false for vertices not yet included in MST

// Update the key only if graph[u][v] is smaller than key[v]

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

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

}

// print the constructed MST

printMST(parent, V, graph);

}

// driver program to test above function

int main()

{

/* Let us create the following graph

2 3

(0)--(1)--(2)

| / \ |

6| 8/ \5 |7

| / \ |

(3)-------(4)

9 */

int graph[V][V] = {{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}};

// Print the solution

primMST(graph);

return 0;

}

OutPut:-

Edge Weight

0 - 1 2

1 - 2 3

0 - 3 6

1 - 4 5

Minimum Spanning tree using Kruskal's Algorithm :-

// C++ program for Kruskal's algorithm to find Minimum Spanning Tree

// of a given connected, undirected and weighted graph

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

// a structure to represent a weighted edge in graph

struct Edge

{

int src, dest, weight;

};

// a structure to represent a connected, undirected

// and weighted graph

struct Graph

{

// V-> Number of vertices, E-> Number of edges

int V, E;

// graph is represented as an array of edges.

// Since the graph is undirected, the edge

// from src to dest is also edge from dest

// to src. Both are counted as 1 edge here.

struct Edge* edge;

};

// Creates a graph with V vertices and E edges

struct Graph* createGraph(int V, int E)

{

struct Graph* graph = new Graph;

graph->V = V;

graph->E = E;

graph->edge = new Edge[E];

return graph;

}

// A structure to represent a subset for union-find

struct subset

{

int parent;

int rank;

};

// A utility function to find set of an element i

// (uses path compression technique)

int find(struct subset subsets[], int i)

{

// find root and make root as parent of i

// (path compression)

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

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

return subsets[i].parent;

}

// A function that does union of two sets of x and y

// (uses union by rank)

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

{

int xroot = find(subsets, x);

int yroot = find(subsets, y);

// Attach smaller rank tree under root of high

// rank tree (Union by Rank)

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

subsets[xroot].parent = yroot;

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

subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and

// increment its rank by one

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

}

// Compare two edges according to their weights.

// Used in qsort() for sorting an array of edges

int myComp(const void* a, const void* b)

{

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

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

return a1->weight > b1->weight;

}

// The main function to construct MST using Kruskal's algorithm

void KruskalMST(struct Graph* graph)

{

int V = graph->V;

struct Edge result[V]; // Tnis will store the resultant MST

int e = 0; // An index variable, used for result[]

int i = 0; // An index variable, used for sorted edges

// Step 1: Sort all the edges in non-decreasing

// order of their weight. If we are not allowed to

// change the given graph, we can create a copy of

// array of edges

qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

// Allocate memory for creating V ssubsets

struct subset *subsets =

(struct subset*) malloc( V * sizeof(struct subset) );

// Create V subsets with single elements

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

{

subsets[v].parent = v;

subsets[v].rank = 0;

}

// Number of edges to be taken is equal to V-1

while (e < V - 1)

{

// Step 2: Pick the smallest edge. And increment

// the index for next iteration

struct Edge next_edge = graph->edge[i++];

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

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

// If including this edge does't cause cycle,

// include it in result and increment the index

// of result for next edge

if (x != y)

{

result[e++] = next_edge;

Union(subsets, x, y);

}

// Else discard the next_edge

}

// print the contents of result[] to display the

// built MST

printf("Following are the edges in the constructed MST\n");

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

printf("%d -- %d == %d\n", result[i].src, result[i].dest,

result[i].weight);

return;

}

// Driver program to test above functions

int main()

{

/* Let us create following weighted graph

10

0--------1

| \ |

6| 5\ |15

| \ |

2--------3

4 */

int V = 4; // Number of vertices in graph

int E = 5; // Number of edges in graph

struct Graph* graph = createGraph(V, E);

// add edge 0-1

graph->edge[0].src = 0;

graph->edge[0].dest = 1;

graph->edge[0].weight = 10;

// add edge 0-2

graph->edge[1].src = 0;

graph->edge[1].dest = 2;

graph->edge[1].weight = 6;

// add edge 0-3

graph->edge[2].src = 0;

graph->edge[2].dest = 3;

graph->edge[2].weight = 5;

// add edge 1-3

graph->edge[3].src = 1;

graph->edge[3].dest = 3;

graph->edge[3].weight = 15;

// add edge 2-3

graph->edge[4].src = 2;

graph->edge[4].dest = 3;

graph->edge[4].weight = 4;

KruskalMST(graph);

return 0;

}

Author

Title

Language

Your paste - Paste your paste here

Minimum Spanning Tree using Prim's Algorithm :-

// A C / C++ program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include &lt;stdio.h&gt;
#include &lt;limits.h&gt;
#include&lt;stdbool.h&gt;
// Number of vertices in the graph
#define V 5

// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v &lt; V; v++)
   if (mstSet[v] == false &amp;&amp; key[v] &lt; min)
       min = key[v], min_index = v;

return min_index;
}

// A utility function to print the
// constructed MST stored in parent[]
int printMST(int parent[], int n, int graph[V][V])
{
printf(&quot;Edge \tWeight\n&quot;);
for (int i = 1; i &lt; V; i++)
   printf(&quot;%d - %d \t%d \n&quot;, parent[i], i, graph[i][parent[i]]);
}

// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
   // Array to store constructed MST
   int parent[V];
   // Key values used to pick minimum weight edge in cut
   int key[V];
   // To represent set of vertices not yet included in MST
   bool mstSet[V];

// Initialize all keys as INFINITE
   for (int i = 0; i &lt; V; i++)
       key[i] = INT_MAX, mstSet[i] = false;

// Always include first 1st vertex in MST.
   // Make key 0 so that this vertex is picked as first vertex.
   key[0] = 0;  
   parent[0] = -1; // First node is always root of MST

// The MST will have V vertices
   for (int count = 0; count &lt; V-1; count++)
   {
       // Pick the minimum key vertex from the
       // set of vertices not yet included in MST
       int u = minKey(key, mstSet);

// Add the picked vertex to the MST Set
       mstSet[u] = true;

// Update key value and parent index of
       // the adjacent vertices of the picked vertex.
       // Consider only those vertices which are not
       // yet included in MST
       for (int v = 0; v &lt; V; v++)

// graph[u][v] is non zero only for adjacent vertices of m
       // mstSet[v] is false for vertices not yet included in MST
       // Update the key only if graph[u][v] is smaller than key[v]
       if (graph[u][v] &amp;&amp; mstSet[v] == false &amp;&amp; graph[u][v] &lt; key[v])
           parent[v] = u, key[v] = graph[u][v];
   }

// print the constructed MST
   printMST(parent, V, graph);
}

// driver program to test above function
int main()
{
/* Let us create the following graph
       2 3
   (0)--(1)--(2)
   | / \ |
   6| 8/ \5 |7
   | /   \ |
   (3)-------(4)
           9       */
int graph[V][V] = {{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}};

// Print the solution
   primMST(graph);

return 0;
}

OutPut:-

Edge   Weight
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5
Minimum Spanning tree using Kruskal's Algorithm :-

// C++ program for Kruskal's algorithm to find Minimum Spanning Tree
// of a given connected, undirected and weighted graph
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

// a structure to represent a weighted edge in graph
struct Edge
{
   int src, dest, weight;
};

// a structure to represent a connected, undirected
// and weighted graph
struct Graph
{
   // V-&gt; Number of vertices, E-&gt; Number of edges
   int V, E;

// graph is represented as an array of edges.
   // Since the graph is undirected, the edge
   // from src to dest is also edge from dest
   // to src. Both are counted as 1 edge here.
   struct Edge* edge;
};

// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
   struct Graph* graph = new Graph;
   graph-&gt;V = V;
   graph-&gt;E = E;

graph-&gt;edge = new Edge[E];

return graph;
}

// A structure to represent a subset for union-find
struct subset
{
   int parent;
   int rank;
};

// A utility function to find set of an element i
// (uses path compression technique)
int find(struct subset subsets[], int i)
{
   // find root and make root as parent of i
   // (path compression)
   if (subsets[i].parent != i)
       subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;
}

// A function that does union of two sets of x and y
// (uses union by rank)
void Union(struct subset subsets[], int x, int y)
{
   int xroot = find(subsets, x);
   int yroot = find(subsets, y);

// Attach smaller rank tree under root of high
   // rank tree (Union by Rank)
   if (subsets[xroot].rank &lt; subsets[yroot].rank)
       subsets[xroot].parent = yroot;
   else if (subsets[xroot].rank &gt; subsets[yroot].rank)
       subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and
   // increment its rank by one
   else
   {
       subsets[yroot].parent = xroot;
       subsets[xroot].rank++;
   }
}

// Compare two edges according to their weights.
// Used in qsort() for sorting an array of edges
int myComp(const void* a, const void* b)
{
   struct Edge* a1 = (struct Edge*)a;
   struct Edge* b1 = (struct Edge*)b;
   return a1-&gt;weight &gt; b1-&gt;weight;
}

// The main function to construct MST using Kruskal's algorithm
void KruskalMST(struct Graph* graph)
{
   int V = graph-&gt;V;
   struct Edge result[V]; // Tnis will store the resultant MST
   int e = 0; // An index variable, used for result[]
   int i = 0; // An index variable, used for sorted edges

// Step 1: Sort all the edges in non-decreasing
   // order of their weight. If we are not allowed to
   // change the given graph, we can create a copy of
   // array of edges
   qsort(graph-&gt;edge, graph-&gt;E, sizeof(graph-&gt;edge[0]), myComp);

// Allocate memory for creating V ssubsets
   struct subset *subsets =
       (struct subset*) malloc( V * sizeof(struct subset) );

// Create V subsets with single elements
   for (int v = 0; v &lt; V; ++v)
   {
       subsets[v].parent = v;
       subsets[v].rank = 0;
   }

// Number of edges to be taken is equal to V-1
   while (e &lt; V - 1)
   {
       // Step 2: Pick the smallest edge. And increment
       // the index for next iteration
       struct Edge next_edge = graph-&gt;edge[i++];

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

// If including this edge does't cause cycle,
       // include it in result and increment the index
       // of result for next edge
       if (x != y)
       {
           result[e++] = next_edge;
           Union(subsets, x, y);
       }
       // Else discard the next_edge
   }

// print the contents of result[] to display the
   // built MST
   printf(&quot;Following are the edges in the constructed MST\n&quot;);
   for (i = 0; i &lt; e; ++i)
       printf(&quot;%d -- %d == %d\n&quot;, result[i].src, result[i].dest,
                                               result[i].weight);
   return;
}

// Driver program to test above functions
int main()
{
   /* Let us create following weighted graph
           10
       0--------1
       | \   |
   6| 5\ |15
       |   \ |
       2--------3
           4   */
   int V = 4; // Number of vertices in graph
   int E = 5; // Number of edges in graph
   struct Graph* graph = createGraph(V, E);

// add edge 0-1
   graph-&gt;edge[0].src = 0;
   graph-&gt;edge[0].dest = 1;
   graph-&gt;edge[0].weight = 10;

// add edge 0-2
   graph-&gt;edge[1].src = 0;
   graph-&gt;edge[1].dest = 2;
   graph-&gt;edge[1].weight = 6;

// add edge 0-3
   graph-&gt;edge[2].src = 0;
   graph-&gt;edge[2].dest = 3;
   graph-&gt;edge[2].weight = 5;

// add edge 1-3
   graph-&gt;edge[3].src = 1;
   graph-&gt;edge[3].dest = 3;
   graph-&gt;edge[3].weight = 15;

// add edge 2-3
   graph-&gt;edge[4].src = 2;
   graph-&gt;edge[4].dest = 3;
   graph-&gt;edge[4].weight = 4;

KruskalMST(graph);

return 0;
}

Private - Private paste aren't shown in recent listings.

Delete After - When should we delete your paste?

Spam protection -

Reply to "Untitled"