граф смежности в c ++ с использованием stl

Question

Я хочу создать представление списка смежности для графа, используя vector и когда мы объявляем vector как глобальную переменную, где память выделяется для вектора в стеке или куче

    #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);

    }

Answer 1

Вместо того, чтобы иметь явный параметр в вашем списке смежности, вы можете собирать данные и поведение в класс.В зависимости от того, насколько разрежен ваш график, доступны различные представления.В отличие от ответа Давиде , я буду использовать 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;
}

Answer 2

gph - это vector из int, поэтому вы не можете получить доступ к методу push_back в graph[u], потому что graph[u] - это int!

Вы можете представить список смежностикак эффективная матрица (2D) из int, где вы можете иметь строки разных размеров.Но в конечном итоге это 2D структура.Это означает, что вы должны объявить свой список смежности как vector<vector<int>>.

Следующий код должен дать вам некоторое представление о том, как он работает:

    #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);
    }