Как найти размер списка смежности графа в C++?

Question

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

Graph.h 
class Graph 
{ 
    long long no_of_nodes; // No. of vertices 
    list<long long> *adj_list_of_nodes; // Pointer to an array containing adjacency lists 

    public: 
    void sizeOfGraph(); 
    void addEdge(long long, long long); // function to add an edge to graph 
    bool isReachable(long long, long long); // returns true if there is a path from s to d 
}; 



Graph.cpp 
void Graph::sizeOfGraph() 
{ 
    adj_list_of_nodes = new list<long long>[1]; 

    //I want to find out the no_of_nodes in the adjacency list somewhat like this but this is not working 
    this->no_of_nodes = adj_list_of_nodes.size(); 
} 

Но поскольку список смежности является списком типов указателей, я не могу найти подходящую функцию для этого. Может ли кто-нибудь предложить, как найти нет узлов на графике или с помощью списка смежности

Answer 1

В случае указателей просто вызовите метод с помощью оператора ->.

adj_list_of_nodes->size(); 

Обратите внимание, что просто, выделяя пространство new не волшебным образом заполнить list. Вам нужно вставить данные в список. Часть инициализации new должна идти в конструкторе вашего класса и в delete в деструкторе. В идеале вы должны использовать класс интеллектуальных указателей вместо необработанных указателей на C++.

Таким образом, 1. Инициализировать указатель в конструкторе. 2. Заполните данные в списке. 3. Верните размер. (Если данные вставлены, тогда размер будет отличным от нуля)

Примечание: Я не понимаю, что нужно для списка <> * здесь. Вы можете просто использовать объект вместо указателя на один, то есть list<long long> adj_list.

Редактировать список смежности имеет вид: [{вершина}: [список смежных вершин ..] ..]

Поэтому создать карту: с ключом в качестве имени вершины (long long в этом случае) и значение как список смежности.

class Graph 
{ 
    std::map<long long, std::list<long long>> adj_list ; 

public: 
    Graph() = default ; 
    void insert(long long, const std::list<long long>&); 
    std::size_t size() const ; 
}; 

void Graph::insert(long long v, const std::list<long long>& lt) { 
    if(adj_list[v].size() == 0u) 
     adj_list[v] = lt ; 
    else 
     adj_list[v].insert(adj_list[v].begin(), lt.begin(), lt.end()); 
} 

std::size_t Graph::size() const { 
    return adj_list.size(); 
} 

int main() { 
    Graph ob ; 
    ob.insert(1, { 2, 3 }); // vertex 2 and 3 are adjacent to vertex 1 
    std::cout << ob.size() ; 
} 

Here - общий пример. (где ваша вершина может быть любым типом данных, то есть a long long, char, std::string)