0

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!

Improve this question
3
  • 7
    Don't use an array, use a std::vector. Commented Apr 10, 2021 at 14:10
  • Marginally related: new subset[(V * sizeof(subset))] is rather suspicious. What's the sizeof for? new is not malloc, and new subset[V] will already allocate the right amount for V entries of type subset. Commented Apr 10, 2021 at 14:11
  • And when you used your debugger to run your program, one line at a time, and inspect the values of all objects, variables, and pointers, what did you see? Commented Apr 10, 2021 at 14:15

1 Answer 1

Reset to default
1

This answer might not answer your question directly but it should shed some light on the problem.

First of all, yes you have a lot of pointer problems...

Secondly, pair ANY use of the new operator with the delete operator. As it stands, you have a bunch of memory leaks.

Also, why create_graph? Create a constructor for Graph instead (and a destructor since the class has an Edge* edge it needs to take care of).

struct Graph { int V; int E; Edge* edge; // constructor Graph(int V, int E) { this->V = V; this->E = E; this->edge = new Edge[E]; } // destructor ~Graph() { // nullify the member variable before deleting its memory is just a safety measure pertaining to multithreading. Edge* _edge = this->edge; this->edge = nullptr; delete _edge; } };

Then change Graph* graph = create_graph(V, E); into Graph* graph = new Graph(V, E); and do delete graph when you're done using it.

Make sure you remove all memory leaks and we can go on to discussing referencing the correct data (f.ex. by me changing my answer).

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.