c++ - 试图理解 C++ 列表

Question

请原谅我的笨拙，但我无法理解以下内容:

class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // A dynamic array of adjacency lists
    void bridgeUtil(int v, bool visited[], int disc[], int low[], int parent[]);

  public:
    Graph(int V);   // Constructor
    void addEdge(int v, int w);   // function to add an edge to graph
    void bridge();    // prints all bridges
};

  Graph::Graph(int V)
  {
      this->V = V;
      adj = new list<int>[V];
  }

  void Graph::addEdge(int v, int w)
  {
     adj[v].push_back(w);
     adj[w].push_back(v);  // Note: the graph is undirected
  }

任何人都可以解释一下这个数据结构是如何工作的以及用以下方式初始化它时会产生什么结果:

  Graph g1(5);
  g1.addEdge(1, 0);
  g1.addEdge(0, 2);
  g1.addEdge(2, 1);
  g1.addEdge(0, 3);
  g1.addEdge(3, 4);

非常感谢!

Answer 1

底层数据结构

std::list 是一个 doubly linked list ，它的行为与 std::vector 类似，除了 vector 基本上是一个动态数组管理系统。

图表

当您创建图表时，您指定图表将具有的节点总数。每个节点都有自己的列表。

当您调用函数 add_edge 时，它会获取索引 v 处的节点(这是一个列表)。然后它将数字 w 添加到该列表，表示存在从节点 v 到节点 w 的链接。在下一个语句中再次发生同样的情况，只是相反。它在索引 w 处获取列表并将数字 v 添加到列表中，表示存在从节点 w 到节点 v 的链接。

由于这种性质，我们找到了注释 //注意:该图是无向的，因为它绘制了从两个节点到另一个节点的路径。

结果

由于每个节点都有自己的列表。我们可以随机选择一个，然后使用如下函数找到连接到它的所有节点。

list<int> Graph::getNodes(int v)
{
   return(adj[v]);
}

你的代码做什么

//Creates 5 lists, each one representing a node with possible id [0 - 4]
Graph g1(5);       
g1.addEdge(1, 0);
g1.addEdge(0, 2);
g1.addEdge(2, 1);
g1.addEdge(0, 3);
g1.addEdge(3, 4);

//Results in 5 lists that look like this
/*
  (NODE) | (NODE) | (NODE) | (NODE) | (NODE)
  adj[0] | adj[1] | adj[2] | adj[3] | adj[4]
---------------------------------------------
    1    |    0   |    0   |    0   |   3
    2    |    2   |    1   |    4   |
    3    |        |        |        |
*/

根据列表，我可以得出结论，从节点 0，我可以到达节点 1、2 和 3