0

Below is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>

using namespace std;

/////////////////////////////////////////////////////////////////////////
/*
// struct Edge
// Represent one edge in the graph. Fields contain
// two vertex numbers and a weight.
*/
struct Edge
{
    int vertex_1, vertex_2, weight;
};
////////////////////////////////////////////////////////////////////////
/*
// struct Graph
// Represents a weighted graph. Fields contain the # of vertices,
// edges,an array of edges, along with it's physical size.
*/
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 vertex_1 to vertex_2 is also edge from vertex_2
    // to vertex_1. Both are counted as 1 edge here.
    struct Edge* edge;
};
//////////////////////////////////////////////////////////////////////////
/*
// manifestGraph
// Represents a graph with vertices and no edges.
*/
struct Graph* manifestGraph(int V, int E)
{

    struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;

    graph->edge = (struct Edge*) malloc(graph->E * sizeof( struct Edge));

    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.vertex_1);
        int y = find(subsets, next_edge.vertex_2);

        // 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].vertex_1,
               result[i].vertex_2, result[i].weight);
    return;
}
//////////////////////////////////////////////////////////////////////////
// Driver program to test above functions
int main()
{

    return 0;
}

I"m trying to get it to print out like the example in this link:

http://www.cs.ecu.edu/~karl/2530/spr17/Assn/Assn4/assn4.html

where is states functional requirements. Can anyone help me with this?

v/r

3
Contributors
6
Replies
20
Views
5 Months
Discussion Span
Last Post by Seif_2
1

This is a bad mixture of C and C++. Also, your main() function does nothing. First question is whether you are are supposed to be writing C or C++ code? If C++, then your structs for Graph and Edge should be classes and not structures. Yes, structs in C++ are classes where all members are public. If that is what you want, then ok. Another issue is that you are not properly encompassing expressions such as using while (e < V - 1) instead of while (e < (V - 1)) - it could possibly be evaluated as while ((e < V) - 1). Always be explicit in what you mean when writing code like this. This sort of code may work 99% of the time. That other 1% will bite you right on the ass! Oops. Sorry but I didn't mean for the rocket to fly into the sun! Doh! Also, if this is supposed to be C++ use operator new instead of malloc(). If you have to, use calloc() instead - at least that way the memory allocated will be cleared to null values.

One final issue (but not the last) is that you don't validate your array boundaries such as in your find() and Union() functions.

So, review all of your code and decide what you are trying to do.

0

write the program for dev c++ to show total value if number1=0,number2=8,value=number1+number2

0

write the program for dev c++ to show total value if number1=0,number2=8,value=number1+number2

0

include<iostream>

using namespace std;
int main()
(
int number1=0, number2=8, value(0);
value=number1+number2;
cout<<number1<<"+"<<number2<<"="<<value<<endl;
system("pause");
return0;
)

find errors and give solution

0

include<iostream>

using namespace std;
int main()
(
int number1=0,number2=8,value(0);
value=number1+number2;
cout<<number1<<"+"<<number2<<"="<<value<<endl;
system("pause");
return0;
)

Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.