Путаница указателей классов C ++ Graph

Question

Я пытаюсь создать класс графа, в котором граф представлен списками смежности. Сам граф представляет собой вектор указателей, каждый из которых указывает на связанный список узлов. По какой-то причине, когда я использую функцию печати графика, программа ничего не выводит. Может ли кто-нибудь показать мне, что я делаю не так и, возможно, в чем мое непонимание указателей? Заранее спасибо!

#include <array>
#include <vector>
#include <tuple>
#include <unordered_map>

class Node
{
    public:

    int vertex;
    int value;
    Node* next;

    Node(int ver)
    {
        vertex = ver;
    };
};

class Graph
{
    public:

    int n_nodes;
    std::unordered_map<int,Node*> graph;
    
    Graph(int n)
    {   
        n_nodes = n;
        for(int i=0;i<n;i++)
        {
            graph.insert({i,nullptr});
        };
    };

    void add_edge(int src,int des,int val)
    {
        Node node_des = Node(des);
        node_des.value = val;
        node_des.next = graph[src];
        graph[src] = &node_des;

        Node node_src = Node(src);
        node_src.value = val;
        node_src.next = graph[des];
        graph[des] = &node_src;
    };

    void print_graph()
    {
        for(int i =0; i<n_nodes;i++)
        {
            std::string str = "Head "+std::to_string(i);
            Node node = *graph[i];
            while (&node != nullptr)
            {
                str=str+" -> "+std::to_string(node.vertex);
                node = *(node.next);
            };

            std::cout<<str<<std::endl;
        };
    };
};

int main()
{
    Graph g = Graph(6);
    g.add_edge(0,1,3);
    g.add_edge(2,1,4);
    g.add_edge(0,4,1);
    g.add_edge(4,5,6);
    g.add_edge(5,3,2);
    g.add_edge(4,3,3);
    g.add_edge(3,2,5);
    g.add_edge(4,1,1);
    g.add_edge(3,1,2);

    g.print_graph();
    return 0;
}```

Answer 1

Если возможно, вы можете просто использовать вектор из вектора вместо связанных списков и вообще не использовать указатели. Поскольку кэш памяти некоторые операции вставки в векторные операции могут быть быстрее, чем связанные списки, такая структура, как:

struct Node2 {
    int vertex; 
    int value;
};

struct Edge2 {
    int src, des, value;
};

struct Graph2 {
    int n_nodes;
    std::vector<std::vector<Node2>> graph; 

    void add_edge(Edge2 edge) {
        graph[edge.src].emplace_back(edge.des, edge.value);
        graph[edge.des].emplace_back(edge.src, edge.value);
    }

    void add_edge(std::initializer_list<Edge2> edges)
    {
        std::for_each(edges.begin(), edges.end(), [this](auto &e) { add_edge(e); });
    };
}

Конечная обработка проще и быстрее, чем связанные списки;

https://quick-bench.com/q/cmX2-2IYA873TR4qn5aV4ijjUQo

Answer 2

Эти изменения внесены благодаря @drescherjm. Проблема заключалась в том, что я создал локальную переменную и ссылался на ее адрес вместо того, чтобы явно создавать указатель и устанавливать его на экземпляр узла new, где время жизни объекта контролируется динамически.

#include <bits/stdc++.h> 
#include <array>
#include <vector>
#include <tuple>
#include <unordered_map>

class Node
{
    public:

    int vertex;
    int value;
    Node* next;

    Node(int ver)
    {
        vertex = ver;
    };
};

class Graph
{
    public:

    int n_nodes;
    std::unordered_map<int,Node*> graph;
    
    Graph(int n)
    {   
        n_nodes = n;
        for(int i=0;i<n;i++)
        {
            graph.insert({i,nullptr});
        };
    };

    void add_edge(int src,int des,int val)
    {
        Node * node_des = new Node(des);
        node_des->value = val;
        node_des->next = graph[src];
        graph[src] = node_des;

        Node * node_src = new Node(src);
        node_src->value = val;
        node_src->next = graph[des];
        graph[des] = node_src;
    };

    void print_graph()
    {
        for(int i =0; i<n_nodes;i++)
        {
            std::string str = "Head "+std::to_string(i);
            Node * node_ptr = graph[i];
            while (node_ptr != nullptr)
            {
                str=str+" -> "+std::to_string(node_ptr->vertex);
                node_ptr = node_ptr->next;
            };
            std::cout<<str<<std::endl;
        };
    };
};

int main()
{
    Graph g = Graph(6);
    g.add_edge(0,1,3);
    g.add_edge(2,1,4);
    g.add_edge(0,4,1);
    g.add_edge(4,5,6);
    g.add_edge(5,3,2);
    g.add_edge(4,3,3);
    g.add_edge(3,2,5);
    g.add_edge(4,1,1);
    g.add_edge(3,1,2);

    g.print_graph();
    return 0;
}