如何在c++中用链表实现图结构

在C++中，通常使用链表数据结构来实现图（Graph），特别是稀疏图，因为链表可以高效地表示节点间的邻接关系。这里我们采用邻接表（Adjacency List）的方式，它将每个顶点（Node）关联到一个链表，链表里存储的是与其相连的所有边所对应的其他顶点。

以下是基本步骤：

1. 定义节点（Vertex）和边（Edge）类：
- 节点类（Vertex）通常包含一个标识符（如整数或字符串）以及指向其邻居节点的链表指针。

   class Vertex {
       int id;
       std::list<Vertex*> neighbors; // 链表用于存储邻居
       // 其他成员函数和构造/析构等...
   };

2. 定义图类（Graph）：
- 图类包含一个节点集合，通常是一个vector或map，存储每个节点及其索引。
- 提供添加节点、删除节点、添加边（连接两个节点）等操作。

   class Graph {
       std::unordered_map<int, Vertex*> vertices; // 通过id查找节点

       void add_vertex(Vertex* vertex);
       void add_edge(int src_id, int dst_id);
       // 其他操作...
   };

3. 实现关键功能：
- `add_vertex`：在图中插入新节点，并更新节点列表。
- `add_edge`：找到源节点并将其邻居列表中的目标节点加入；反之亦然（如果有必要的话，双向链接）。
- 搜索、遍历（DFS/BFS）、删除节点及边等。

void Graph::add_vertex(Vertex* vertex) {
   vertices[vertex->id] = vertex;
}

void Graph::add_edge(int src_id, int dst_id) {
   auto& src = vertices[src_id];
   auto& dst = vertices[dst_id];
   src.neighbors.push_back(dst);
   dst.neighbors.push_back(src); // 双向链接，若不需要则仅保留一个方向
}