深入解析：如何在 C++ 中高效实现图数据结构

2026-02-08 21:28:54 0条评论 1次阅读 0人点赞

在系统设计、算法竞赛以及日常的开发工作中，我们经常遇到需要处理复杂网络关系的情况。无论是社交网络中的好友关系，还是地图导航中的路径规划，这些都离不开一种强大的非线性数据结构——图。在 C++ 中，灵活且高效地实现图结构，是每一位进阶开发者必须掌握的技能。

在这篇文章中，我们将深入探讨图的两种核心实现方式：邻接矩阵 和 邻接表。我们不仅会学习它们的基础代码实现，还会剖析它们在内存、时间和实际应用场景中的差异，帮助你做出最合适的技术选择。

图的基本概念回顾

在正式开始之前，让我们快速统一一下认知。图是由 顶点 和 边 组成的集合。如果边是有方向的（比如 A 关注了 B，但 B 没关注 A），我们称之为有向图；如果边没有方向（比如 A 和 B 是朋友），则是无向图。此外，边还可以带有 权重，例如两个城市之间的距离。

在 C++ 的标准模板库（STL）中，并没有直接提供一个名为 Graph 的容器，但这给了我们极大的自由度去根据需求定制实现。一般来说，最主流的实现方式有两种。

方法一：使用邻接矩阵实现图

什么是邻接矩阵？

邻接矩阵是表示图中顶点之间关系最直观的方式。想象一下，我们创建了一个二维表格（即二维数组或 INLINECODE28a986f3）。如果顶点 INLINECODEcebd51e6 和顶点 INLINECODE349947fb 之间有边相连，我们就将在矩阵的第 INLINECODE57056227 行第 j 列的位置标记为 1（或者是权重值），否则标记为 0。

核心逻辑

要构建一个邻接矩阵，我们需要遵循以下规则：

  • 初始化：创建一个 INLINECODE5d813090 的二维向量（INLINECODE5cf567da），其中 n 是顶点的数量。初始化时，将所有元素设为 0，表示初始状态下没有任何连接。
  • 添加边（无向图）：如果要在顶点 INLINECODEe4305721 和顶点 INLINECODE9562ed88 之间添加一条边，我们需要同时更新 INLINECODE60c26af7 和 INLINECODE0cfd8991。这是因为无向图的边是双向的。
  • 添加边（有向图）：如果是有向图，边是从 INLINECODE4691a2ab 指向 INLINECODE25f03add 的，那么我们只需要设置 matrix[u][v] = 1。
  • 权重处理：如果是加权图，我们将 matrix[u][v] 设置为具体的权重值，而不是简单的 1。

C++ 代码实现：基于类的封装

让我们来看一个完整的例子。我们将使用 C++ 的类来封装图的逻辑，这样做符合面向对象的设计思想，代码也更易于维护。

在这个例子中，我们实现一个无向图，并添加打印矩阵的功能，方便我们调试和查看结果。

// C++ Program to Implement a Graph Using Adjacency Matrix
#include 
#include 
using namespace std;

class Graph {
    // 使用二维向量存储邻接矩阵
    // 这里的 int 可以改为 double 以支持浮点权重
    vector<vector> adjMatrix;

public:
    // 构造函数：初始化图，n 是顶点的数量
    Graph(int n) {
        // 创建一个 n x n 的矩阵，并初始化所有值为 0
        adjMatrix = vector<vector>(n, vector(n, 0));
    }

    // 添加边的函数：在顶点 u 和 v 之间建立连接
    void addEdge(int u, int v) {
        // 检查顶点是否越界是一个好习惯（生产环境代码中建议加上）
        if (u >= 0 && u = 0 && v < adjMatrix.size()) {
            adjMatrix[u][v] = 1;
            adjMatrix[v][u] = 1; // 无向图需要反向设置，有向图则去掉此行
        }
    }

    // 打印邻接矩阵的函数
    void printGraph() {
        cout << "图的邻接矩阵表示：" << endl;
        int n = adjMatrix.size();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << adjMatrix[i][j] << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    // 创建一个包含 4 个顶点的图 (0, 1, 2, 3)
    int n = 4;
    Graph g(n);

    // 添加边，构建示例图的拓扑结构
    // 对应关系：0-1, 0-2, 1-3, 2-3
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);

    // 打印矩阵查看结果
    g.printGraph();

    return 0;
}

输出结果：

图的邻接矩阵表示：
0 1 1 0 
1 0 0 1 
1 0 0 1 
0 1 1 0

性能分析与应用场景

从代码中我们可以看出，邻接矩阵的实现非常简洁。但是，我们需要权衡它的利弊：

  • 时间复杂度：查询两个顶点之间是否有边是非常快的，只需要 INLINECODE29cf5600 的时间，直接访问数组下标即可。但是，如果要遍历一个顶点的所有邻居，我们需要遍历整行，这需要 INLINECODEb3f48c90 的时间（V 是顶点数）。
  • 空间复杂度：这是邻接矩阵最大的痛点。无论图中实际有多少条边，我们都需要 O(V^2) 的空间来存储矩阵。即使图是空的（没有边），只要顶点 V 在，空间就被占用了。

实际应用建议：如果你的图非常密集（边的数量接近顶点数量的平方），或者你需要频繁检查两点间是否存在连接，邻接矩阵是首选。但在处理稀疏图时，它可能会浪费大量内存。

—

方法二：使用邻接表实现图

为什么选择邻接表？

为了解决邻接矩阵在稀疏图中浪费内存的问题，我们引入了 邻接表。你可以把它想象成通讯录：每个人（顶点）都对应一个列表，里面记录了他的所有朋友（邻居）。如果一个人没有朋友，他的列表就是空的，不占用额外空间。

核心逻辑

邻接表通常使用数组的链表来实现，但在 C++ 中，我们更习惯使用 vector，因为它在内存中是连续的，访问速度更快。

  • 数据结构：我们创建一个大小为 INLINECODEc9493912 的 INLINECODE9ef17cce，其中每个元素本身又是一个 INLINECODEaec24320（即 INLINECODEe88de37a，或者使用 INLINECODEe33ddf5b 和 INLINECODEf56049ff）。外层向量的索引代表顶点，内层向量存储该顶点的所有邻居。
  • 添加边（无向图）：如果要在 INLINECODE54b425e2 和 INLINECODE711921e5 之间加边，我们将 INLINECODE0d997c17 加入 INLINECODE6e14ead2 的列表，同时将 INLINECODEad796167 加入 INLINECODEe7883d8a 的列表。
  • 添加边（有向图）：只需将 INLINECODE01439362 加入 INLINECODEd6f79d15 的列表即可。

C++ 代码实现：更高效的内存管理

下面的代码展示了如何使用 STL 的 vector 来实现邻接表。注意代码中对内存利用的优化。

// C++ Program to Implement a Graph Using Adjacency List
#include 
#include 
using namespace std;

class Graph {
    int numVertices; // 顶点的总数
    // 这是一个数组的数组，adjList[i] 存储顶点 i 的所有邻接顶点
    vector<vector> adjList;

public:
    // 构造函数：初始化邻接表的大小
    Graph(int vertices) {
        numVertices = vertices;
        // 调整外层 vector 的大小为 vertices，默认每个内层 vector 为空
        adjList.resize(vertices);
    }

    // 添加边的函数
    void addEdge(int u, int v) {
        // 无向图：互相添加
        // 如果是有向图（u -> v），只执行下一行即可
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }

    // 打印邻接表的函数
    void printGraph() {
        cout << "图的邻接表表示：" << endl;
        for (int i = 0; i < numVertices; i++) {
            cout << "顶点 " << i << ": ";
            // 使用范围 for 循环遍历邻居
            for (int neighbor : adjList[i]) {
                cout < " << neighbor << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    // 创建一个包含 5 个顶点的图
    Graph g(5);

    // 构建图结构
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    // 打印邻接表
    g.printGraph();

    return 0;
}

输出结果：

图的邻接表表示：
顶点 0: -> 1 -> 4 
顶点 1: -> 0 -> 2 -> 3 -> 4 
顶点 2: -> 1 -> 3 
顶点 3: -> 1 -> 2 -> 4 
顶点 4: -> 0 -> 1 -> 3

性能分析

邻接表是大多数算法题和实际工程中的首选实现方式。

  • 空间复杂度：O(V + E)。我们只存储存在的边，这使得它在处理稀疏图时比邻接矩阵极其节省内存。
  • 时间复杂度：获取两个点之间是否有边稍微慢一点（O(degree(u))，即邻居的数量），但遍历一个顶点的所有邻居非常快，直接遍历列表即可，这通常是图算法（如 BFS, DFS）中最常见的操作。

进阶应用：处理加权图

在实际开发中，我们经常遇到加权图。例如，在实现导航算法时，边的权重代表距离或时间。我们可以非常方便地修改上述的邻接表实现来支持权重。

我们需要引入一个简单的辅助结构体或使用 pair 来存储数据。

#include 
#include 
#include  // for std::pair
using namespace std;

class WeightedGraph {
    int V;
    // 每个元素是一个 pair，first 是邻居顶点，second 是边的权重
    vector<vector<pair>> adjList;

public:
    WeightedGraph(int vertices) {
        V = vertices;
        adjList.resize(V);
    }

    // 添加带权重的边
    void addEdge(int u, int v, int weight) {
        adjList[u].push_back(make_pair(v, weight));
        adjList[v].push_back(make_pair(u, weight)); // 假设是无向图
    }

    void printGraph() {
        cout < (邻居, 权重)）：" << endl;
        for (int i = 0; i < V; i++) {
            cout << "顶点 " << i << ": ";
            for (auto &neighbor : adjList[i]) {
                cout < (" << neighbor.first << ", " << neighbor.second << ") ";
            }
            cout << endl;
        }
    }
};

int main() {
    int V = 4;
    WeightedGraph g(V);

    // 添加边：0-1 权重 5, 0-2 权重 3 ...
    g.addEdge(0, 1, 5);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 2);
    g.addEdge(2, 3, 6);

    g.printGraph();
    return 0;
}

实战中的最佳实践与常见陷阱

在多年的编程实践中，我们总结了一些在使用 C++ 实现图时的实用建议，希望能帮你避开弯路：

  • 选择正确的 STL 容器：虽然我们通常用 INLINECODEfcbdf618，但如果图中涉及大量的顶点删除操作（不仅仅是边），或者由于某种原因顶点 ID 不是连续的整数，使用 INLINECODE1191a658 可能会更安全，尽管它会有 O(log V) 的额外开销。
  • 警惕递归深度：在图上实现深度优先搜索（DFS）时，如果你习惯写递归代码，要注意图的大小。对于一个包含 10^5 个节点的线性图，递归可能会导致 栈溢出。在这种情况下，建议使用显式的栈数据结构来实现迭代式的 DFS。
  • 1-indexed 还是 0-indexed：很多算法题目或问题描述为了符合人类直觉（节点从 1 开始编号），会使用 1-indexed。但 C++ 的数组是 0-indexed。一个常见的技巧是在初始化图时，直接分配 n + 1 个空间，这样可以忽略下标 0，直接映射输入的节点号，从而减少下标转换的错误。
  • 预留空间优化：如果你知道图大概会有多少条边，可以在创建 INLINECODEaeb1b5fe 时使用 INLINECODE61effe37 方法。这虽然不改变逻辑复杂度，但能减少 vector 动态扩容时的内存拷贝次数，对于构建超大规模图时，性能提升非常明显。

总结：你该选择哪种方式？

让我们做一个简单的总结，以便你在未来的项目中快速做出决策：

  • 选择邻接矩阵：当你需要快速判断任意两点是否相连（O(1)），或者图是一个 稠密图（边数非常多）时。另外，如果你需要频繁地进行修改操作（如切换边的状态），矩阵也可能更方便。
  • 选择邻接表：在绝大多数 算法竞赛 和 实际工程 中，尤其是处理 稀疏图 时。它节省内存，遍历邻居效率高，是“性价比”最高的选择。

掌握这两种实现方式，只是图算法之旅的起点。有了这个坚实的基础，接下来你就可以放心地去探索更复杂的算法，如最短路径、最小生成树以及网络流了。希望这篇文章能帮助你清晰地理解如何在 C++ 中构建图，祝你在编码的旅途上一帆风顺！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/37311.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年