adjacency graph in c++ using stl

Question

I want to make adjacency list representation of graph using vector and when we declare vector as global variable where the memory is allocated to vector in stack or heap

    #include<bits/stdc++.h>
    #include<vector>
    using namespace std;


    void addedge(vector<int> &graph, int u, int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void printgraph(const vector<int> &gph) {
        for (int v = 0 : gph) {
            cout << v;
            for (auto x : gph[v]) {
                cout << x;
                printf("\n");
            }
        }
    }

    int main() {
        vector<int> gph;
        addedge(gph, 2, 3);
        addedge(gph, 6, 7);
        addedge(gph, 1, 2);
        printgraph(gph);

    }

Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) As well as [Why is “using namespace std” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Some programmer dude, Nov 26 '18 at 08:29
Please reread [ask]. In particular, use interpunction between sentences and end a question with a question mark. Also, state your problem clearly, that part is far from clear! — Ulrich Eckhardt, Nov 26 '18 at 09:07

Davide Spataro · Accepted Answer · 2018-11-26T09:43:50.727

3

gph is a vector of int so you cannot access the method push_back in graph[u] because graph[u] is a int!

You can imagine an adjacency list as a space efficient matrix(2D) of int where you can have rows of different sizes. But ultimately it is a 2D structure. This means you have to declare your adjacency list as a vector<vector<int>>.

The following code should give you some indication on how it works:

    #include<iostream>
    #include<vector>

    using Graph = std::vector<std::vector<int>>;

    void addedge(Graph &graph, const int u, const int v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    void printgraph(const Graph &gph) {

        for (int node = 0 ; node < gph.size() ; node++) {
            std::cout<<node<<" : ";
              for (auto x : gph[node]) {
                std::cout << x << " ";
            }
            std::cout<<std::endl;
        }   
    }

    int main() {
        Graph gph(8, std::vector<int>());
        addedge(gph, 2, 3);
        addedge(gph, 6, 7);
        addedge(gph, 1, 2);

        printgraph(gph);
    }

edited Nov 26 '18 at 09:43

answered Nov 26 '18 at 09:01

Davide Spataro

7,319
1
24
36

Even better would be to use using: using Vector2D = std::vector >; – M. Denninger Nov 26 '18 at 09:02
@M.Denninger I disagree, in a Vector2D I would expect an `x` and `y` member (function). – rubenvb Nov 26 '18 at 09:04
Of course a class for that would be even better, however I think that is beyond the scope of this little exercise here, don't you think? – M. Denninger Nov 26 '18 at 09:05
If the graph is dense enough (or small enough), a `std::vector` is another option (typically simpler and faster). – Acorn Nov 26 '18 at 09:05
@M.Denninger *"Even better would be to use using: using Vector2D = std::vector >;"* No, aliasing complex types like that is not a good idea. That name is also very wrong: nobody expects that type nor interface from a `Vector2D`, which typically represents a pair of reals as in an actual math vector. – Acorn Nov 26 '18 at 09:07
`int node = 0 ; node < gph.size() ; node++` why cannot we use auto here? – Nov 26 '18 at 09:20
2

@humblefool you can use range based loop here as well, but I wanted to print the index of the node we are currently processing – Davide Spataro Nov 26 '18 at 09:22
somone also suggested me of using like `auto &x` can you tell me something about about this will this prints the address – Nov 26 '18 at 09:25
@humblefool That is a different question. Comments are not the right place for this. Search on SO, I am sure it is plenty of answers regarding this problem. If not, you can always ask a new question. – Davide Spataro Nov 26 '18 at 09:28
You should add an error check for addedge() to have a better answer. – tunglt Nov 26 '18 at 09:29
`using Graph = std::vector>;` can you tell me why you added this line your program – Nov 26 '18 at 10:21
what is that concept called ?looking similar to `typedef` @DavideSpataro – Nov 26 '18 at 10:23
It is an alias. You are given to the long and hard to type `std::vector>` another name. You can use `Graph` and `std::vector>` as if they are the exact same type. – Davide Spataro Nov 26 '18 at 10:44

score 0 · Answer 2 · answered Nov 26 '18 at 10:02

Rather than having an explicit parameter of your adjacency list, you could collect the data and behaviour into a class. Depending on how sparse your graph is, there are various representations available. To contrast with Davide's answer, I'll use std::multimap<int, int>.

class Graph
{
    std::multimap<int, int> edges;
public:
    void addedge(int u, int v)
    {
        edges.insert(u, v);
        edges.insert(v, u);
    }

    friend std::ostream& operator<<(std::ostream& os, const Graph & graph)
    {
        for (auto v_it = graph.begin(), v_end = {}; v_it != graph.end(); v_it = v_end)
        {
            v_end = graph.upper_bound(v_it->first);
            os << v_it->first << " : ";
            for (auto it = v_it; it != v_end; ++it)
            {
                os << it->second << " ";
            }
            os << std::endl;
        }
        return os;
    }
}

int main() {
    Graph gph;

    gph.addedge(2, 3);
    gph.addedge(6, 7);
    gph.addedge(1, 2);
    std::cout << graph;
}

adjacency graph in c++ using stl

2 Answers2