Question

In: Computer Science

C Programming Question: Q) Write a C - program to implement an Uprooted version (Save to...

C Programming Question:

Q) Write a C - program to implement an Uprooted version (Save to parent pointer instead of child pointer, ie. parent of top is null) of Kruskal's Minimum Spanning Tree with adjacency list and min-heap as the additional data structure.

Note: Please implement it in C and also keep the above conditions in mind. You can take your time. Thank you.

Solutions

Expert Solution

// 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 && i < graph->E)

    {

        // 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;

}


Related Solutions

C Programming Question: Q) Write a C - program to check whether a given graph is...
C Programming Question: Q) Write a C - program to check whether a given graph is Bipartite using Breadth-first search (adjacency list) Do take your time but please do post full code and also please do it in C.
C Programming Question: Write a C - program to implement the following three operations: a) Breadth-first...
C Programming Question: Write a C - program to implement the following three operations: a) Breadth-first search using Adjacency List b) Breadth-first search using Adjacency Matrix c) Check whether a given graph is Bipartite using Breadth-first search (adjacency list).​​​​​​ Please take your time, but do submit the correct and full code. Thank you very much.
Write a C++ program where you implement a synchronized multithreaded version of HAPPY with four threads....
Write a C++ program where you implement a synchronized multithreaded version of HAPPY with four threads. The program will take in an array from 1 to n (n = 50) and will be passed to four different threads: If the current number is divisible by 2, then print HAP If the current number is divisible by 5, then print PY If the current number is divisible by both 2 and 5, then print HAPPY If the number is neither divisible...
write pseudocode not c program If- else programming exercises 1.    Write a C program to find...
write pseudocode not c program If- else programming exercises 1.    Write a C program to find maximum between two numbers. 2.    Write a C program to find maximum between three numbers. 3.    Write a C program to check whether a number is negative, positive or zero. 4.    Write a C program to check whether a number is divisible by 5 and 11 or not. 5.    Write a C program to check whether a number is even or odd. 6.    Write...
Write and test a C program to implement Bubble Sort. . In your C program, you...
Write and test a C program to implement Bubble Sort. . In your C program, you should do: Implement the array use an integer pointer, get the size of the array from standard input and use the malloc function to allocate the required memory for it. Read the array elements from standard input. Print out the sorted array, and don’t forget to free the memory. Debug your program using Eclipse C/C++ CDT.
PRACTICAL 10 C PROGRAMMING. Question 1 - Reading into a dynamic array. Write a program called...
PRACTICAL 10 C PROGRAMMING. Question 1 - Reading into a dynamic array. Write a program called temperatures01 that reads a (non-empty) sequence maximum daily temperatures. Your program should first ask for the number of temperatures to read and dynamically allocate an array just big enough to hold the number of temperatures you read. You should then read in the elements of the array using a loop. You then should print out the elements of the array in reverse order (from...
C++ programming question Write a program that will read input from a text file called "theNumbers.txt"...
C++ programming question Write a program that will read input from a text file called "theNumbers.txt" (you will have to provide your own when debugging). The text file that is to be opened is formatted a certain way, namely, there is always one integer, one character (representing an operation), another integer, and then a new line character, with spaces between each item. A sample text file is provided below. theNumbers.txt 144 + 26 3 * 18 88 / 4 22...
Write a program to implement and analyzing the Bubble Sort. a. Write a C++ function for...
Write a program to implement and analyzing the Bubble Sort. a. Write a C++ function for Bubble Sort b. Use a dynamic array of integers in a variable size of n. c. Display the following information: 1) Total counts of comparisons 2) Total counts of shifts / moves / swaps, whichever applies d. Write a main() function to test a best, and an average cases in terms of time efficiency i. Fill out the array with random numbers for an...
Write a complete C program that read the text below and save the text in a...
Write a complete C program that read the text below and save the text in a new file "second.txt" with the same text written in all uppercase. "Beedle the Bard was an English wizard and author of wizarding fairytales. Beedle was born in Yorkshire, England. At some point in his life he wrote The Tales of Beedle the Bard . The only known image of Beedle is a woodcut that shows him with a "luxuriant" beard. Beedle wrote in ancient...
Programming in C++ Write a program that prints the values in an array and the addresses...
Programming in C++ Write a program that prints the values in an array and the addresses of the array’s elements using four different techniques, as follows: Array index notation using array name Pointer/offset notation using array name Array index notation using a pointer Pointer/offset notation using a pointer Learning Objectives In this assignment, you will: Use functions with array and pointer arguments Use indexing and offset notations to access arrays Requirements Your code must use these eight functions, using these...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT