试图理解一个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是一个双向链表,其行为类似于std::vector除了向量基本上是动态数组管理系统.

图表

创建图形时,指定图形将具有的节点总数.每个节点都有自己的列表.

当您调用该函数时,add_edge它会在索引处获取节点(这是一个列表)v.然后它将该数字添加w到该列表,表示从节点v到节点之间存在链接w.除了相反之外,在下一个陈述中再次发生同样的情况.它在索引处抓取列表w并将该数字添加v到列表中,表示从节点w到节点之间存在链接v.

正是由于这种性质,我们找到了评论// Note: the graph is undirected,因为它绘制了从两个节点到另一个节点的路径.

结果

由于每个节点都有自己的列表.我们可以随机选择一个,并通过使用如下所示的函数找到连接到它的所有节点.

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    |        |        |        |
*/

基于这些清单,我可以得出结论,从中Node 0我可以得到Nodes 1, 2 and 3