C++如何使用STL容器实现图形数据结构

STL容器通过vector、map等提供高效内存管理，支持邻接矩阵（O(V²)空间）和邻接表（O(V+E)空间）实现图结构，前者适合稠密图且边查询O(1)，后者节省稀疏图空间并优化遍历性能；带权图可用vector或自定义结构体存储权重，有向图仅单向添加边；BFS用queue、DFS用stack、Dijkstra用priority_queue结合vector实现高效算法操作。

STL容器在C++中是实现图数据结构的核心工具，无论是选择邻接矩阵还是邻接表，

std::vector

std::map

std::unordered_map

在C++中实现图数据结构，我们通常有两种主流思路：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。STL容器为这两种方法提供了强大的支持，让我们可以专注于图的逻辑而非底层的内存管理。

邻接矩阵

邻接矩阵是一个二维数组，

matrix[i][j]

i

j

std::vector>

N x N

vector

立即学习“C++免费学习笔记（深入）”；

// 无权图的邻接矩阵
std::vector> adjMatrix(numNodes, std::vector(numNodes, false));

// 添加边 (u, v)
void addEdgeMatrix(int u, int v, std::vector>& matrix) {
    if (u >= 0 && u < matrix.size() && v >= 0 && v < matrix.size()) {
        matrix[u][v] = true;
        // 如果是无向图，还需要 matrix[v][u] = true;
    }
}

使用

std::vector>

std::vector

邻接表

邻接表则是更常用于稀疏图的表示方法。它是一个数组，数组的每个元素都是一个链表（或

vector

std::vector>

std::vector>

// 无权图的邻接表
std::vector> adjList(numNodes);

// 添加边 (u, v)
void addEdgeList(int u, int v, std::vector>& list) {
    if (u >= 0 && u < list.size() && v >= 0 && v < list.size()) {
        list[u].push_back(v);
        // 如果是无向图，还需要 list[v].push_back(u);
    }
}

对于带权图，邻接表可以存储

std::pair

在我看来，选择哪种实现方式，很大程度上取决于图的密度和我们主要进行的图操作。

邻接表与邻接矩阵：STL容器如何权衡性能与空间？

在图数据结构的选择上，邻接表和邻接矩阵各有千秋，而STL容器的运用直接影响了它们在性能和空间上的表现。在我日常处理图问题时，这往往是我首先会思考的问题。

邻接矩阵，用

std::vector>

std::vector>

邻接表，通常用

std::vector>

std::vector>

push_back

vector

std::set

vector

std::set

我个人觉得，在大多数实际应用中，尤其是处理大规模图时，邻接表因其更优的空间效率和在遍历邻居时的性能优势，往往是更受欢迎的选择。只有在V很小，或者需要频繁进行O(1)的边存在性检查时，邻接矩阵才会显得更有吸引力。

如何用STL容器实现带权图和有向图？

实现带权图和有向图，STL容器同样提供了非常灵活的方案，基本上是在前面无权无向图的基础上进行一些数据结构上的扩展。这并不是什么特别复杂的事情，更多的是一种设计上的选择。

带权图 (Weighted Graphs)

对于带权图，我们需要在表示边的同时，存储一个权重值。

BlackBox AI

AI编程助手，智能对话问答助手

下载

• 邻接矩阵实现： 我们可以将

  std::vector>

  替换为

  std::vector>

  （或

  double

  等），其中

  matrix[u][v]

  存储的是边

  (u,v)

  的权重。为了表示两个节点之间没有边，我们需要约定一个特殊的“无限大”值（例如

  INT_MAX

  或

  -1

  ），避免与实际权重混淆。

  // 带权图的邻接矩阵
  const int INF = std::numeric_limits::max();
  std::vector> weightedAdjMatrix(numNodes, std::vector(numNodes, INF));
  
  void addWeightedEdgeMatrix(int u, int v, int weight, std::vector>& matrix) {
      if (u >= 0 && u < matrix.size() && v >= 0 && v < matrix.size()) {
          matrix[u][v] = weight;
          // 如果是无向图，matrix[v][u] = weight;
      }
  }

• 邻接表实现： 这是我个人觉得更优雅的方式。我们可以让邻接表存储

  std::pair

  ，其中

  first

  是目标节点，

  second

  是权重。或者，定义一个简单的结构体来封装这些信息，让代码更具可读性。

  // 带权图的邻接表
  struct Edge {
      int to;
      int weight;
  };
  std::vector> weightedAdjList(numNodes);
  
  void addWeightedEdgeList(int u, int v, int weight, std::vector>& list) {
      if (u >= 0 && u < list.size() && v >= 0 && v < list.size()) {
          list[u].push_back({v, weight});
          // 如果是无向图，list[v].push_back({u, weight});
      }
  }

  这种方式在遍历邻居时能直接获取权重，非常方便。

有向图 (Directed Graphs)

有向图的实现实际上比带权图更简单，它主要体现在边的添加逻辑上。

• 邻接矩阵实现： 当添加一条从

  u

  到

  v

  的有向边时，我们只设置

  matrix[u][v] = true

  （或权重），而不需要设置

  matrix[v][u]

  。这与无向图的区别仅在于

  addEdge

  函数内部的逻辑。

• 邻接表实现： 同样，当添加一条从

  u

  到

  v

  的有向边时，我们只在

  adjList[u]

  中添加

  v

  （或

  (v, weight)

  ），而不需要在

  adjList[v]

  中添加

  u

  。

  // 有向带权图的邻接表（基于上面的Edge结构体）
  // std::vector> directedWeightedAdjList(numNodes);
  
  void addDirectedWeightedEdgeList(int u, int v, int weight, std::vector>& list) {
      if (u >= 0 && u < list.size() && v >= 0 && v < list.size()) {
          list[u].push_back({v, weight}); // 只添加一个方向
      }
  }

  所以说，有向图的实现更多的是一种约定，而不是对底层数据结构的大幅改动。

在图遍历算法中，STL容器如何提升效率？

图遍历算法，比如广度优先搜索（BFS）和深度优先搜索（DFS），以及一些最短路径算法（如Dijkstra），STL容器简直是它们的“最佳搭档”，极大简化了实现并提升了效率。

广度优先搜索 (BFS)

BFS的核心思想是层层推进，这天然需要一个队列来存储待访问的节点。

std::queue

push

front

pop

// BFS伪代码
std::queue q;
std::vector visited(numNodes, false); // 跟踪访问状态

q.push(startNode);
visited[startNode] = true;

while (!q.empty()) {
    int u = q.front();
    q.pop();
    // 处理节点 u

    // 遍历 u 的所有邻居
    for (int v : adjList[u]) { // adjList 是 std::vector>
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

这里，邻接表

adjList

std::vector

std::vector

visited

深度优先搜索 (DFS)

DFS可以使用递归实现（利用函数调用栈），也可以显式使用

std::stack

std::stack

push

top

pop

// DFS显式栈实现伪代码
std::stack s;
std::vector visited(numNodes, false);

s.push(startNode);
visited[startNode] = true;

while (!s.empty()) {
    int u = s.top();
    s.pop();
    // 处理节点 u

    for (int v : adjList[u]) {
        if (!visited[v]) {
            visited[v] = true;
            s.push(v);
        }
    }
}

和BFS一样，

std::vector

visited

Dijkstra算法 (最短路径)

Dijkstra算法需要不断选择当前距离源点最近的未访问节点，这正是优先队列

std::priority_queue

// Dijkstra伪代码 (使用邻接表)
std::priority_queue, std::vector>, std::greater>> pq; // pair: {distance, node}
std::vector dist(numNodes, INF); // 存储最短距离

dist[startNode] = 0;
pq.push({0, startNode});

while (!pq.empty()) {
    int d = pq.top().first;
    int u = pq.top().second;
    pq.pop();

    if (d > dist[u]) continue; // 已经找到更短路径

    for (const auto& edge : weightedAdjList[u]) { // weightedAdjList 是 std::vector>
        int v = edge.to;
        int weight = edge.weight;
        if (dist[u] + weight < dist[v]) {
            dist[v] = dist[u] + weight;
            pq.push({dist[v], v});
        }
    }
}

std::priority_queue

std::vector

dist

说实话，STL容器在图算法中的作用，我觉得就像是给算法装上了高效的齿轮。正确地选择和使用它们，不仅能让代码更简洁、可读，还能显著提升算法的运行效率，这对于处理大规模图数据来说至关重要。