c++ 图的邻接表表示 c++图数据结构实现

邻接表用vector<vector<int>>存储无向图，addEdge双向添加边，print遍历输出；带权图用vector<vector<pair<int,int>>>存边权，适合稀疏图，空间省、遍历快。

在C++中实现图的邻接表表示，是一种高效且常用的方式，尤其适合稀疏图（边数远小于顶点数平方）的存储和操作。邻接表使用数组或vector配合链表（或vector）来存储每个顶点的邻接顶点，既能节省空间，又能方便地遍历邻居节点。

邻接表的基本结构

一个无向图或有向图可以用以下方式建模：

• 用一个vector<vector<int>> 来表示每个顶点连接的其他顶点。
• 如果是带权图，可以用 vector<vector<pair<int, int>>>，其中 pair 的第一个值是邻接点，第二个是边的权重。
• 顶点编号通常从0或1开始。

基础实现：无向无权图

#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 print() const {
        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.print();
    return 0;
}

扩展：有向带权图

如果需要处理有向图或带权图，可以修改邻接表为存储 pair 或自定义结构体。

凡人网络购物系统jsp版(JspShop)

基于jsp+javabean+access(mysql)三层结构的动态购物网站，v1.2包含v1.0中未公开的数据库连接 的java源文件 一，网站前台功能： 产品二级分类展示：一级分类－－二级分类－－产品列表－－详细介绍（名称，图片，市场价，会员价，是否推荐，功能介绍等） 产品搜索：关键字模糊搜索 定购产品：选择商品－－确认定购－－填写收货人信息－－选择付款方式－－订单号自动生成（限登录用户）

0

查看详情

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

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

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

    // 添加有向边 u -> v，权重 w
    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
    }

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

};

关键点说明

• 使用 vector<vector<T>> 是最常见做法，动态扩容，代码简洁。
• 对于稀疏图，邻接表比邻接矩阵更节省内存。
• 遍历某个顶点的所有邻居时间复杂度为 O(度)，效率高。
• 若频繁查询两点是否有边，可考虑搭配哈希表优化，但一般DFS/BFS不需要。
• 支持快速插入边，删除边稍麻烦（需在vector中erase），如需频繁删除可用 list 替代 inner vector。

以上就是c++++ 图的邻接表表示 c++图数据结构实现的详细内容，更多请关注php中文网其它相关文章！