Kruskal Algorithm convert with vector

Question

I've a question, I'm working on a implementation of Kruskal Algorithm, i finished it, and it's working, but there's a problem, i've used a "static" array 2D, (input by user, but Limited to 100). How can i convert it in dynamic allocation or using vector? I prefer vector, but i don't know how to "modify, and insert" item in a vector of vector. Anyone can help me? Thanks, Bye

There's the code:

class kruskal
{
private:
    int n; //no of nodes
    int noe; //no edges in the graph
    int graph_edge[100][4];

    int tree[10][10];

    int sets[100][10];
    int top[100];
public:
    int read_graph();
    void initialize_span_t();
    void sort_edges();
    void algorithm();
    int find_node(int );
    void print_min_span_t();
};

int kruskal::read_graph()
{
cout<<"This program implements the kruskal algorithm\n";
cout<<"Enter the no. of nodes in the undirected weighted graph";
cin>>n;
noe=0;

cout<<"Enter the weights for the following edges ::\n";

for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
        cout<<i<<" , "<<j;
        int w;
        cin>>w;
            if(w!=0)
            {
            noe++;
            graph_edge[noe][1]=i;
            graph_edge[noe][2]=j;
            graph_edge[noe][3]=w;
        }
    }
}
// print the graph edges
cout<<"\n\nThe edges in the given graph are::\n";
for(int i=1;i<=noe;i++)
{
    cout<<" < "<<graph_edge[i][1]
    <<" , "<<graph_edge[i][2]
    <<" > "<<graph_edge[i][3]<<endl;

}
}

void kruskal::sort_edges()
{
/**** Sort the edges using bubble sort in increasing order**************/
for(int i=1;i<=noe-1;i++)
{
    for(int j=1;j<=noe-i;j++)
    {
        if(graph_edge[j][3]>graph_edge[j+1][3])
        {
        int t=graph_edge[j][1];
        graph_edge[j][1]=graph_edge[j+1][1];
        graph_edge[j+1][1]=t;

        t=graph_edge[j][2];
        graph_edge[j][2]=graph_edge[j+1][2];
        graph_edge[j+1][2]=t;

        t=graph_edge[j][3];
        graph_edge[j][3]=graph_edge[j+1][3];
        graph_edge[j+1][3]=t;
    }
}
}

// print the graph edges

cout<<"\n\nAfter sorting the edges in the given graph are::\n";
for(int i=1;i<=noe;i++)
cout<<""<< graph_edge[i][1]
<<" , "<<graph_edge[i][2]
<<" > ::"<<graph_edge[i][3]<<endl;
}

void kruskal::algorithm()
{
    // ->make a set for each node
    for(int i=1;i<=n;i++)
    {
    sets[i][1]=i;
    top[i]=1;
    }

cout<<"\nThe algorithm starts ::\n\n";

for(int i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);

    if(p1!=p2)
    {
        cout<<"The edge included in the tree is ::"
        <<" < "<<graph_edge[i][1]<<" , "
        <<graph_edge[i][2]<<" > "<<endl<<endl;

        tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
        tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];

        // Mix the two sets

        for(int j=1;j<=top[p2];j++)
        {
            top[p1]++;
            sets[p1][top[p1]]=sets[p2][j];
        }

        top[p2]=0;
    }
    else
    {
        cout<<"Inclusion of the edge "
        <<" < "<<graph_edge[i][1]<<" , "
        <<graph_edge[i][2]<<" > "<<"forms a cycle so it is removed\n\n";
    }
}
}

int kruskal::find_node(int n)
{
    for(int i=1;i<=noe;i++)
    {
        for(int j=1;j<=top[i];j++)
        {
        if(n==sets[i][j])
            return i;
        }
    }

return -1;
}

void kruskal::print_min_span_t()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
    cout<<tree[i][j]<<"\t";
cout<<endl;
}
}

Answer 1

You can create struct or class edge;

struct Edge {
    int v, u, w;

    Edge(int v, int u, int w) : v(v), u(u), w(w) {}

    bool operator < (const Edge& c) const{
         if (w != c.w)
             return w < c.w;
         if (v != c.v)
             return v < c.v;
         return u < c.u;
    }
}

Then you can store graph as vector of edges

vector<edge> es;
....
cin >> v >> u >> w;
if (w != 0) {
    es.push_back(Edge(v, u, w));
}

Also, because operator < is defined in class Edge, you can sort edges using built-in C++ sort algorithm

#include <algorithm>
....
std::sort(es.begin(), es.end());