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

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

定义节点（Vertex）和边（Edge）类：

节点类（Vertex）通常包含一个标识符（如整数或字符串）以及指向其邻居节点的链表指针。class Vertex {
int id;
std::list<Vertex*> neighbors; // 链表用于存储邻居
// 其他成员函数和构造/析构等...
};
登录后复制

定义图类（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);
  // 其他操作...


};

登录后复制

实现关键功能：

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&amp; src = vertices[src_id];
   auto&amp; dst = vertices[dst_id];
   src.neighbors.push_back(dst);
   dst.neighbors.push_back(src); // 双向链接，若不需要则仅保留一个方向
}
登录后复制