Adjacency List (Double vector) to solve graph algorithm

Question

So I am using a double vector with data type pair<int, int> to store both the edge and weight of a vertex in a graph. With this implementation, I am trying to solve Prims Algorithm. The process of getting the first edge seems easy but the repetition loop to get the rest of the edges seems to be not working properly. For the specific graph in this code, the output is supposed to be ({2,4}, {5,6}, {4,5}, {3,4}, {2,3}, {2,7}). I am getting ({2,4}, {5,6}, {4,5}, {3,4}, {2,3}, {2,3}). Here is the code:

#include <iostream>
#include<vector>
#include <utility>
using namespace::std;

class graphs{
private:
    vector<vector<pair<int, int>>> graph;
    int vertices;

public:
    graphs(int v){
        vertices = v;
        graph = vector<vector<pair<int, int>>>(v+1);
    }
    void insert(int v, int e, int w=0){
        graph[v].push_back(make_pair(e, w));
    }

    void prim(){
        int edges = vertices - 1, e = 0, min = 1000, u, v;
        int t[2][vertices]; // array to insert the edges
        vector<pair<int, int>> check (vertices+1);
        for(int i = 1; i<graph.size(); i++){
            for(int j = 0; j<graph[i].size(); j++){
                if(graph[i][j].second<min){
                    min = graph[i][j].second; u = i; v = graph[i][j].first;
                }
            }
        } // This for loop gets the original min value and index.
        t[0][e] = u; t[1][e] = v; check[u].first = check[v].first =-1; check[u].second = check[v].second = 1000;

        for(int i = 1; i<check.size(); i++){
            min = 1000;
            if(check[i].first != -1){
                for(int j = 0; j< graph[i].size(); j++){
                    if(graph[i][j].first == t[0][e] && graph[i][j].second<min){
                        min = graph[i][j].second; u = i; v = t[0][e];
                    }
                    else if(graph[i][j].first == t[1][e] && graph[i][j].second<min){
                        min = graph[i][j].second; u = i; v = t[1][e];
                        check[i].second = graph[i][j].second;
                    }
                }
                check[i].first = v; check[i].second = min;
                if(min == 1000){
                    check[i].first = t[1][e]; check[i].second = 1000;
                }
                else{
                    check[i].first = v; check[i].second = min;
                }
            }
        }//This for loop adjusts the check vector to show whether the rest of the vertices are closer to t[0][0] or t[1][0]
        e++;
        while(e<edges){// The repetition loop.
            min = 1000;
            for(int i = 1; i< vertices; i++){
                if(check[i].second < min && check[i].first != -1){
                    min = check[i].second; u=i; v = check[i].first;
                }
            }//This for loop finds the next min edge to put into the final array t.
            t[0][e]= u; t[1][e] = v;
            check[u].first = -1;
            for(int i = 1; i<check.size(); i++){ //This for loop adjusts the check vector in accordance with the new vertex.
                if(check[i].first != -1){
                    for(int j = 0; j< graph[i].size(); j++){
                        if(graph[i][j].first == u && graph[i][j].second<check[i].second){
                            min = graph[i][j].second;
                        }
                    }
                    check[i].first = u; check[i].second = min;
                }
            }
            e++;
        }
        for(int i = 0; i<2; i++){
            for(int j = 0; j< vertices-1; j++){
                cout<<t[i][j] << " ";
            }
            cout<< endl;
        }
    }
};
int main(int argc, const char * argv[]){
    graphs graph(7);
    graph.insert(1, 2, 25);
    graph.insert(1, 6, 5);
    graph.insert(2,1, 25);
    graph.insert(2,3, 12);
    graph.insert(2, 7, 10);
    graph.insert(3, 2, 12);
    graph.insert(3, 4, 8);
    graph.insert(4, 3, 8);
    graph.insert(4, 5, 16);
    graph.insert(4, 7, 14);
    graph.insert(5, 4, 16);
    graph.insert(5, 6, 20);
    graph.insert(5, 7, 18);
    graph.insert(6, 1, 5);
    graph.insert(6, 5, 20);
    graph.insert(7,2,10);
    graph.insert(7, 4, 14);
    graph.insert(7, 5, 18);
    graph.prim();
    return 0;
}

Any general critique and tips will be greatly appreciated as well!

"seems to be buggy" what makes you think so? Do you get wrong output for some input? Please incldue more information in the question — 463035818_is_not_an_ai, Nov 26 '20 at 15:02
*but the repetition loop to get the rest of the edges seems to be buggy* -- Is it buggy? What bugs are there? Have you used a debugger? One thing you could do: get rid of the `vertices` member variable -- it isn't necessary once you have a `vector`, since `vector::size()` tells you how many items are in the vector. — PaulMcKenzie, Nov 26 '20 at 15:03
`int t[2][vertices]; // array to insert the edges` -- And why isn't this a vector also? That line of code is not valid C++. — PaulMcKenzie, Nov 26 '20 at 15:04
That code has various syntax errors, such as attempting to create a `std::vector>` with initial value of 0, variable length array usage, and an improper placement of `else` statements due to you putting more than one statement per line. Please fix this. And in general, [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [what is a debugger](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — PaulMcKenzie, Nov 26 '20 at 15:11
I added the vertices member variable so that I would not have to subtract 1 each time. — thekvector, Nov 26 '20 at 15:14
@thekvector The code doesn't compile. Please fix the code. When you post code, it has to be a [mcve]. As to the `vertices` member -- all you are doing when you add that unnecessary variable is open up yourself for bugs to occur. Why do you need to keep track of the size? What if the size changes, and you forget to update that variable? The `size()` is function is never wrong. — PaulMcKenzie, Nov 26 '20 at 15:15
Okay sorry, it was a whole larger class with like 20 functions and i was deleting specifically for this question and misplaced brackets, but it should be working now! — thekvector, Nov 26 '20 at 15:24

score 0 · Answer 1 · answered Nov 26 '20 at 17:05

while(e<edges){// The repetition loop.
            min = 1000;
            for(int i = 1; i< vertices; i++){
                if(check[i].second < min && check[i].first != -1){
                    min = check[i].second; u=i; v = check[i].first;
                }
            }

The i has to be less than or equal to vertices.

            min = 1000;
            for(int i = 1; i<= vertices; i++){
                if(check[i].second < min && check[i].first != -1){
                    min = check[i].second; u=i; v = check[i].first;
                }
            }

Adjacency List (Double vector) to solve graph algorithm

1 Answers1