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

STL容器通过vector、map等提供高效内存管理，支持邻接矩阵（O(V²)空间）和邻接表（O(V+E)空间）实现图结构，前者适合稠密图且边查询O(1)，后者节省稀疏图空间并优化遍历性能；带权图可用vector<pair<int,int>>或自定义结构体存储权重，有向图仅单向添加边；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

是否存在边，或者边的权重。在C++中，

std::vector<std::vector<int>>

是实现邻接矩阵最直观的方式。例如，对于一个包含N个节点的图，我们可以声明一个

N x N

的

vector

：

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

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

使用

std::vector<std::vector<bool>>

是个不错的选择，因为

std::vector<bool>

有特化优化，能节省空间。

邻接表

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

vector

），存储与该节点相邻的所有节点。在C++中，

std::vector<std::vector<int>>

或

std::vector<std::list<int>>

是典型的实现方式。

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

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

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

std::pair<int, int>

（目标节点，权重）或自定义结构体。

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

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

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

邻接矩阵，用

std::vector<std::vector<bool>>

或

std::vector<std::vector<int>>

实现时，它的空间复杂度是O(V^2)，V是图中节点的数量。这意味着无论图中有多少边，它都会占用固定的V*V大小的空间。这对于节点数量不大的稠密图（边数接近V^2）来说非常高效，因为每个存储单元都被充分利用。但对于节点很多、边很少的稀疏图，大部分空间会是空的，造成显著的浪费。性能上，判断两个节点之间是否存在边是O(1)操作，这得益于数组的随机访问特性。添加或删除边也是O(1)。然而，遍历一个节点的所有邻居则可能需要O(V)时间，因为它需要扫描整个行。

邻接表，通常用

std::vector<std::vector<int>>

或

std::vector<std::list<int>>

来实现，其空间复杂度是O(V+E)，V是节点数，E是边数。这对于稀疏图来说是巨大的优势，它只存储实际存在的边，极大地节省了空间。例如，一个有1000个节点但只有2000条边的图，邻接表会比邻接矩阵节省很多内存。性能方面，添加边通常是O(1)（

push_back

到

vector

末尾）或O(logD)（如果用

std::set

来保证邻居唯一性并排序，D是该节点的度数）。遍历一个节点的所有邻居是O(D)操作，其中D是该节点的度数，这比邻接矩阵的O(V)通常要快得多。但是，判断两个节点之间是否存在边，如果只是简单

vector

，最坏情况需要O(D)来线性扫描，如果用

std::set

则可以达到O(logD)。

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

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

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

带权图 (Weighted Graphs)

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

Post AI

博客文章AI生成器

50 查看详情

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

  std::vector<std::vector<bool>>

  替换为

  std::vector<std::vector<int>>

  （或

  double

  等），其中

  matrix[u][v]

  存储的是边

  (u,v)

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

  INT_MAX

  或

  -1

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

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

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

  std::pair<int, int>

  ，其中

  first

  是目标节点，

  second

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

  // 带权图的邻接表
  struct Edge {
      int to;
      int weight;
  };
  std::vector<std::vector<Edge>> weightedAdjList(numNodes);
  
  void addWeightedEdgeList(int u, int v, int weight, std::vector<std::vector<Edge>>& 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<std::vector<Edge>> directedWeightedAdjList(numNodes);
  
  void addDirectedWeightedEdgeList(int u, int v, int weight, std::vector<std::vector<Edge>>& 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<int>

就是为这个目的而生的。它提供了

push

、

front

和

pop

等O(1)操作，完美契合BFS的需求。

// BFS伪代码
std::queue<int> q;
std::vector<bool> 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<std::vector<int>>
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

这里，邻接表

adjList

的

std::vector<int>

部分，使得遍历一个节点的所有邻居非常高效，因为它只迭代实际存在的边，而不是像邻接矩阵那样遍历整个行。

std::vector<bool>

作为

visited

数组，提供了O(1)的访问和修改效率。

深度优先搜索 (DFS)

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

std::stack<int>

。

std::stack<int>

同样提供O(1)的

push

、

top

和

pop

操作。

// DFS显式栈实现伪代码
std::stack<int> s;
std::vector<bool> 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::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq; // pair: {distance, node}
std::vector<int> 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<std::vector<Edge>>
        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

在这里以O(logN)的复杂度提供了高效的提取最小元素操作，而

std::vector

作为

dist

数组和邻接表，则保证了O(1)的距离更新和高效的邻居遍历。

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

以上就是C++如何使用STL容器实现图形数据结构的详细内容，更多请关注知识资源分享宝库其它相关文章！

相关标签： node edge 工具 ai c++ 区别 red 封装 结构体 递归 bool int double 数据结构 栈 map 算法 大家都在看： C++如何使用模板实现泛型工具函数 C++中this指针在类成员函数中是如何工作的 C++内存泄漏检测工具使用技巧 C++工厂模式与抽象工厂区别解析 C++开发环境配置调试工具使用技巧