Need help applying Kruskal's Algorithm to an existing adjacency matrix program that uses a 2D struct to store the data

Question

Link to runnable program and program requirements/specs:

https://github.com/edgr-sanchez/CSCE2110-Graph

I've thus far implemented 95% of the program. Everything runs properly and has been tested using the provided test file.

The only thing that I'm having trouble implementing is Kruskal's Algorithm, and this is because I'm not quite sure how I need to use my existing data structure to pass it through Kruskal's.

To clarify a few things: Running Kruskal's Algorithm in this program is not supposed to make changes to the existing data, it should only calculate the minimum spanning tree and print it out.

Running the kruskal command on my program should output the minimum spanning tree in adjacency list format including the street name (S##) and the distance, like this:

NH    NK(S02,11)    NP(S03,13)
NK    NH(S02,11)    NL(S01,24)
NL    NK(S01,24)
NM    NW(S05,15)
NP    NH(S03,13)    NW(S07,12)
NW    NM(S05,15)    NP(S07,12)

The location where I need to implement this is in /src/SanE_10_P3_AdjacencyMatrix.cpp line 208.

Anyways, I'm providing my code and all this information to help you understand my code. I do not expect it to be written for me. I'd love to simply have some guidance on how to implement this using my existing struct:

struct {
    bool exists = false;
    std::string name = "";
    int distance = empty;
} node[MAXNODES][MAXNODES];

This is the current output as well as the remaining expected output:

https://i.sstatic.net/Gv8D4.png

Thanks in advance!

Answer 1

At first I want to make a note: in fact, your node array describes edges, not nodes. Nodes here are indexes. Anyway, I leave the name as is. I presume that your graph is undirected. Here is how Kruskal algorithm can be implemented with your structure.

Define the function:

 std::vector<std::pair<int, int>> kruskal() 
 {
     std::vector<std::pair<int, int>> mst; //our result

At the very beginning we split all the vertices to separate trees. Each tree is identified by an index. We create a lookup table treesByVertex for finding an index of a tree by vertex.

    std::map<int, std::set<int>> trees;
    std::map<int, int> treeByVertex;
    for (int i = 0; i < MAXNODES; ++i)
    {
        std::set<int> tree; // a tree containing a single vertex
        tree.emplace(i); 
        trees.emplace(i, tree); //at startup, the index of a tree is equaled to the index of a vertex
        treeByVertex.emplace(i, i);
    }

Then we create a helper structure edges that will contain a list of edges with ascending distances:

    std::multimap<int, std::pair<int, int>> edges;
    for (int i = 1; i < MAXNODES; ++i)
        for (int j = 0; j < i; ++j)
            if (node[i][j].exists)
                edges.emplace(node[i][j].distance, std::make_pair(i, j));

Iterate over all the edges in ascending order and test if it connects two different trees. If it's true, we add this edge to mst and merge these two trees:

    for (const auto& e : edges)
    {
        int v1 = e.second.first;
        int v2 = e.second.second;
        if (treeByVertex[v1] != treeByVertex[v2]) //use our lookup table to find out if two vertexes belong to different trees
        {
            mst.emplace_back(v1, v2); //the edge is in mst
            trees[v1].insert(trees[v2].begin(), trees[v2].end()); //merge trees
            for (int v : trees[v2]) //modify lookup table after merging
                treeByVertex[v] = treeByVertex[v1];
        }
    }

    return mst;
}

In fact, you even don't need trees container here at all.