How to return structure array in C++

  array-of-structures, c++, pointers, structure

So I’ve been trying to implement Kruskal’s algorithm, first I want to make clear the question is not related to the implementation of the algorithm. I’ve created one graph.hpp file, one kruskalsAlgo.hpp and main.cpp as follows respectively:

#pragma once

struct Edge
{
    int source;
    int destination;
    int weight;
};

struct Graph
{
    int V;
    int E;

    Edge* edge;
};

Graph* create_graph(int V, int E)
{
    Graph* graph = new Graph;
    graph -> V = V;
    graph -> E = E;

    graph -> edge = new Edge[E];

    return graph;
}
#include <stdlib.h>
#include <tuple>

#include "../Graph/Graph.hpp"

class Kruskals_Algo
{
    private:
        struct subset
        {
            int parent;
            int rank;
        };

        void make_set(subset*, int);
        int find_set(subset*, int);
        void _union(subset*, int, int);
    
    public:
        Edge* kruskal(Graph*);
        void print_kruskals_MST(Edge*, int);
};

void Kruskals_Algo::make_set(subset* subsets, int V)
{
    subsets[V].parent = V;
    subsets[V].rank = 0;
}

int Kruskals_Algo::find_set(subset* subsets, int V)
{
    if(subsets[V].parent != V)
        subsets[V].parent = find_set(subsets, subsets[V].parent);
    
    return subsets[V].parent;
}

void Kruskals_Algo::_union(subset* subsets, int x, int y)
{
    int xroot = find_set(subsets, x);
    int yroot = find_set(subsets, y);

    if(subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    
    else if(subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;

    else
    {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

inline int myComp(const void* a, const void* b)
{
    Edge* a1 = (Edge*)a;
    Edge* b1 = (Edge*)b;
    return a1 -> weight > b1 -> weight;
}

Edge* Kruskals_Algo::kruskal(Graph* graph)
{
    int V = graph -> V;
    Edge result[V];
    Edge* result_ptr = result;
    int e = 0;
    int i = 0;

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

    subset* subsets = new subset[(V * sizeof(subset))];

    for (int v = 0; v < V; ++v)
        make_set(subsets, v);

    while(e < V - 1 && i < graph -> E)
    {
        Edge next_edge = graph -> edge[i++];

        int x = find_set(subsets, next_edge.source);
        int y = find_set(subsets, next_edge.destination);

        if (x != y)
        {
            result[e++] = next_edge;
            _union(subsets, x, y);
        }
    }
    //return std::make_tuple(res, e);
    return result_ptr;
}

void Kruskals_Algo::print_kruskals_MST(Edge* r, int e)
{
    int minimumCost = 0;
    for(int i=0; i<e; ++i)
    {
        std::cout << r[i].source << " -- "
                  << r[i].destination << " == "
                  << r[i].weight << std::endl;
        minimumCost = minimumCost + r[i].weight;
    }
    
    std::cout << "Minimum Cost Spanning Tree: " << minimumCost << std::endl;
}
#include <iostream>

#include "Graph/Graph.hpp"

#include "Kruskals_Algo/kruskalsAlgo.hpp"
//#include "Prims_Algo/primsAlgo.hpp"

using namespace std;

class GreedyAlgos
{        
    public:
        void kruskals_mst();
        //void prims_mst();
};

void GreedyAlgos::kruskals_mst()
{
    Kruskals_Algo kr;
    int V;
    int E;
    int source, destination, weight;
    
    cout << "nEnter the number of vertices: ";
    cin >> V;
    cout << "nEnter the number of edges: ";
    cin >> E;
    
    Edge* res;

    Graph* graph = create_graph(V, E);

    for(int i=0; i<E; i++)
    {
        cout << "nEnter source, destinstion and weight: ";
        cin >> source >> destination >> weight;
        graph -> edge[i].source = source;
        graph -> edge[i].destination = destination;
        graph -> edge[i].weight = weight;
    }

    //std::tie(result, E) = kr.kruskal(graph);
    res = kr.kruskal(graph);
    kr.print_kruskals_MST(res, E);
}

int main()
{
    int choice;
    GreedyAlgos greedy;
    greedy.kruskals_mst();
    
    return 0;
}

So my question here is when I debug the program the values in Edge result[V], which is a structure array, are calculated correctly, at position [0] [1] [2] as in the following picture:

enter image description here

but when the function print_kruskals_MST(res, E) is called from the main the values printed are different:

enter image description here

Is there any pointer thing that I’m doing wrong?
Thanks in advance!
P.S. Ignore the comments!

Source: Windows Questions C++

LEAVE A COMMENT