Блог

Я хочу спросить, почему он рассматривает list<int> *adj как массив списков смежности. Я думаю, что это всего лишь динамический массив, но не массив списков? Кто-нибудь может мне объяснить, пожалуйста?

 // Program to print BFS traversal from a given 
// source vertex. BFS(int s) traverses vertices  
// reachable from s. 
#include<iostream> 
#include <list> 
  
using namespace std; 
  
// This class represents a directed graph using 
// adjacency list representation 
class Graph 
{ 
    int V;    // No. of vertices 
  
    // Pointer to an array containing adjacency 
    // lists 
    list<int> *adj;    
public: 
    Graph(int V);  // Constructor 
  
    // function to add an edge to graph 
    void addEdge(int v, int w);  
  
    // prints BFS traversal from a given source s 
    void BFS(int s);   
}; 
  
Graph::Graph(int V) 
{ 
    this->V = V; 
    adj = new list<int>[V]; 
} 
  
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); // Add w to v’s list. 
} 
  

Я хочу спросить, почему он считает, что list<int> *adj; это массив списков смежности ….

Это не массив, это указатель на list<int> . Указатели не являются массивами.

Я думаю, что это всего лишь динамический массив, но не массив списков?

Это не динамический массив.

Что автор пытается сказать, но очень неуклюже, так это то, что указатель в конечном итоге укажет на область в памяти, которая будет содержать непрерывный буфер std::list<int> объектов, отсюда и использование термина «динамический массив».

В примере буфер создается с помощью строки:

adj = new list<int>[V];

в Graph конструкторе. Это создает V std::list<int> объекты в непрерывной памяти и adj будет указывать на первый в списке.

Проблема с кодом заключается в том, что автор мог бы использовать лучший инструмент для этой работы: std::vector<std::list<int>> .

Использование std::vector приведет

1. Избавьтесь от использования необработанных указателей.
2. Значительно упрощает обработку динамических массивов.
3. Делает код, который вы пишете, меньше и менее подвержен ошибкам.
4. Устраняя необходимость в new[] и delete[]

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

Вот перезапись Graph класса:

 #include <iostream> 
#include <list> 
#include <vector>

class Graph 
{ 
   std::vector<std::list<int>> adj;    

public: 
    Graph(int V); 
    void addEdge(int v, int w);  
    void BFS(int s);   
}; 
  
Graph::Graph(int V) : adj(V) {}
 
void Graph::addEdge(int v, int w) 
{ 
    adj[v].push_back(w); 
    // and if you want to add some debugging for boundary conditions, 
    // replace previous line with
    // adj.at(v).push_back(w);
} 
  

Весь этот класс можно безопасно использовать в любом контексте. Обратите внимание, что в V переменной-члене нет необходимости, поскольку adj.size() известно, что V такое.