尝试理解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);

非常感谢！

- vu ngoc

---

我应该假设列表是标准库中的 std::list 吗？如果是这样，那么注释是错误的 - 它不是动态数组。它是一个列表。 - Kevin

实际上，@Kevin，它是一个不可变的std::lists数组。唯一“动态”的部分是数组大小在构造时未知。 - Ti Strga

显然是因为老师不想在发给学生的代码中使用向量。 - Ti Strga

调试器会很乐意地向您解释当您逐步执行时发生了什么。 - kfsone

@Ti Strga - 明白了。没有认真看星号。 - Kevin

Answer 1

底层数据结构

std::list 是一个双向链表，与 std::vector 类似，但 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    |        |        |        |
*/

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

- Kirk Backus

---

非常感谢您详细的回答。实际上，我运行了一个调试器，在添加最后一条边（3,4）之后，它显示在g1中，list<int> adj <3 items>，这就是我感到困惑的地方。 - vu ngoc

Answer 2

请查看维基百科的文章，简而言之，图由节点和边组成。节点是“地方”或“事物”，而边是它们之间的连接。您的代码使用列表的列表来表示这一点。列表x包含所有与节点x相连的节点。

您的示例图将如下所示：

- Cannoliopsida

Answer 3

图形是由节点和节点之间的边组成的集合。在这里，每个节点都是一个数字。每个节点的边缘都用列表表示（列表中的每个条目都是边的另一端的节点）。节点0的相邻节点在邻接数组中的列表0中。在两个节点之间添加一条边后，你会有一条连接这两个节点的边缘。画出来可能会有帮助。你的图形将如下所示：

0--1
|\ |
| \|
3--2
|
4

- Michelle

Answer 4

它跟踪一个图，可能使用邻接映射或链表。在添加了5条边之后，该图将包含以下顶点：{0、1、2、3、4}，并且将从{1-0、0-2、2-1、0-3、3-4}具有边缘。您需要更多详细信息吗？

我不确定它实际上是如何存储的，但两种可能的方式是邻接映射或链表。

邻接映射：

\ 0 1 2 3 4 
0| 0 1 1 1 0 
1| 1 0 1 0 0 
2| 1 1 0 0 0
3| 1 0 0 0 1
4| 0 0 0 1 0 

0表示顶点之间没有连接，1表示它们之间有连接。

链表：

0 > 1, 2, 3
1 > 0, 2
2 > 0, 1
3 > 0, 4
4 > 3

这意味着0会到达1、2和3，而4只会到达3。

- Zac

---

好的，请问在添加了这5条边后，列表会包含什么内容？当我们添加这些边时，这个函数会发生什么呢？ adj[v].push_back(w); adj[w].push_back(v); - vu ngoc

请注意，这是一张无向图，addEdge() 函数会将条目添加到两个邻接表中。 - Michelle

我为您添加了一些更多的信息。@vungoc - Zac

Answer 5

每个Graph实例中都有固定数量的std::list。在您的示例中，数组中有5个。该数字不会改变。

数组中的每个条目都是一个双向链接的int列表。

在X和Y之间添加边缘会更改两个std::list。 X处的数组索引是X的节点列表，并添加T。 Y处的数组索引是Y的节点列表，并添加X。

如果您想要演练...请问您的老师，因为这显然是作业。 :-)

- Ti Strga

---

非常感谢，我现在明白了。尽管它看起来很明显，但实际上这不是作业 :-) - vu ngoc

Answer 6

enter code here

// 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; 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. 
    } 
    
    void Graph::BFS(int s) 
    { 
        // Mark all the vertices as not visited 
        bool *visited = new bool[V]; 
        for(int i = 0; i < V; i++) 
            visited[i] = false; 
    
        // Create a queue for BFS 
        list<int> queue; 
    
        // Mark the current node as visited and enqueue it 
        visited[s] = true; 
        queue.push_back(s); 
    
        // 'i' will be used to get all adjacent 
        // vertices of a vertex 
        list<int>::iterator i; 
    
        while(!queue.empty()) 
        { 
            // Dequeue a vertex from queue and print it 
            s = queue.front(); 
            cout << s << " "; 
            queue.pop_front(); 
    
            // Get all adjacent vertices of the dequeued 
            // vertex s. If a adjacent has not been visited, 
            // then mark it visited and enqueue it 
            for (i = adj[s].begin(); i != adj[s].end(); ++i) 
            { 
                if (!visited[*i]) 
                { 
                    visited[*i] = true; 
                    queue.push_back(*i); 
                } 
            } 
        } 
    } 
    
    // Driver program to test methods of graph class 
    int main() 
    { 
        // Create a graph given in the above diagram 
        Graph g(5); 
        g.addEdge(1, 0); 
        g.addEdge(0, 2); 
        g.addEdge(2, 1); 
        g.addEdge(0, 3); 
        g.addEdge(3, 4);
        
    // g.addEdge(3, 3); 
    
        cout << "Following is Breadth First Traversal "
            << "(starting from vertex 2) \n"; 
        g.BFS(2); 
    
        return 0; 
    } 

- Nikhil Yadav