c++中如何实现图的邻接表_c++图邻接表实现方法-C++-PHP中文网

c++中如何实现图的邻接表_c++图邻接表实现方法

裘德小鎮的故事

发布： 2025-09-28 20:47:01

原创

532人浏览过

使用vector实现邻接表是C++中表示图的常用方法，适合稀疏图。1. 基本结构为vector<vector<int>>，每个顶点对应一个存储邻接点的动态数组；2. 无向图每条边在两个顶点中各存一次，有向图只在起点存储；3. 带权图使用vector<vector<pair<int, int>>>，存储邻接点和权重；4. 初始化时指定顶点数并合理添加边，避免越界；5. vector相比list内存连续、缓存友好，遍历效率高，适用于DFS、BFS等算法。

c++中如何实现图的邻接表_c++图邻接表实现方法

在C++中实现图的邻接表，通常使用标准模板库（STL）中的vector和list来存储每个顶点的邻接顶点。这种方式灵活、高效，适合稀疏图的表示。

邻接表的基本结构

邻接表本质上是一个数组（或vector），其中每个元素对应一个顶点，并保存与该顶点相连的所有边的信息。对于无向图，每条边会在两个顶点中各出现一次；对于有向图，只在起点处记录。

常用的数据结构是：vector<vector<int>> 或 vector<list<int>>。现代C++开发中更推荐使用vector，因为其内存连续、缓存友好。

基本实现步骤

以下是构建一个无向图的邻接表表示的完整示例：

爱图表

AI驱动的智能化图表创作平台

查看详情

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

#include <iostream>
#include <vector>
using namespace std;

class Graph {
private:
    int V; // 顶点数量
    vector<vector<int>> adj; // 邻接表

public:
    Graph(int vertices) : V(vertices), adj(vertices) {}

    // 添加边（无向图）
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // 有向图则去掉这一行
    }

    // 打印邻接表
    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << i << ": ";
            for (int neighbor : adj[i]) {
                cout << neighbor << " ";
            }
            cout << endl;
        }
    }
};

// 使用示例
int main() {
    Graph g(5); // 创建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;
}

登录后复制

带权图的邻接表实现

如果图是带权的，就不能只存邻接顶点，还需要存储对应的边权。可以使用vector<pair<int, int>>，其中第一个值是邻接点，第二个是权重。

class WeightedGraph {
private:
    int V;
    vector<vector<pair<int, int>>> adj; // 邻接表：{目标顶点, 权重}

public:
    WeightedGraph(int vertices) : V(vertices), adj(vertices) {}

    void addEdge(int u, int v, int weight) {
        adj[u].push_back({v, weight});
        adj[v].push_back({u, weight}); // 无向图，有向图则省略
    }

    void printGraph() {
        for (int i = 0; i < V; ++i) {
            cout << "顶点 " << i << ": ";
            for (auto& edge : adj[i]) {
                cout << "(" << edge.first << "," << edge.second << ") ";
            }
            cout << endl;
        }
    }
};

登录后复制