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

裘德小鎮的故事

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

562人浏览过

来源于php中文网

原创

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

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

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

邻接表的基本结构

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

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

基本实现步骤

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

Napkin AI

Napkin AI 可以将您的文本转换为图表、流程图、信息图、思维导图视觉效果，以便快速有效地分享您的想法。

下载

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

#include 
#include 
using namespace std;

class Graph {
private:
    int V; // 顶点数量
    vector> 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>，其中第一个值是邻接点，第二个是权重。

class WeightedGraph {
private:
    int V;
    vector>> 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;
        }
    }
};

常见注意事项

实现邻接表时需注意以下几点：

初始化时确保vector大小正确，避免越界访问
添加边时检查顶点编号是否在有效范围内
若频繁删除边，可考虑使用list替代vector
对于大规模图，注意内存使用和遍历效率

基本上就这些。用vector实现邻接表简单直观，适合大多数图算法场景，比如DFS、BFS、Dijkstra等。

c++输入输出流 c++ cin与cout格式化输出【方法】

c++如何使用std::bind绑定函数参数_c++ 占位符std::placeholders使用【详解】

c++ namespace命名空间用法_c++避免命名冲突

c++20的std::format怎么用比printf更安全高效的格式化方法【详解】

C++中的std::shared_from_this有什么用？C++安全获取this的shared_ptr【智能指针】

c++速学教程(入门到精通)

c++怎么学习？c++怎么入门？c++在哪学？c++怎么学才快？不用担心，这里为大家提供了c++速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！

下载

相关标签:

c++ edge ai ios stream c++开发 int 数据结构算法

本站声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

上一篇：c++ map和unordered_map的性能比较_c++ map与unordered_map性能对比下一篇：c++怎么理解虚函数表vtable_c++虚函数表vtable解析

作者最新文章

MacBook电池健康度怎么看_延长Mac电池寿命的技巧【分享】

2025-12-30 16:08

手机怎么抓拍【技巧】

2025-12-30 16:09

火狐浏览器插件怎么安装_Firefox附加组件安装和管理教程【扩展】

2025-12-30 16:19

siri有什么好玩的用法功能【推荐】

2025-12-30 16:21

c++如何实现并查集算法_c++ 路径压缩与按秩合并优化【案例】

2025-12-30 16:23

Win11怎么创建桌面快捷方式_Windows 11网页与程序快捷方式制作【详解】

2025-12-30 16:27

电脑摄像头怎么打开电脑前置摄像头的打开方式【教程】

2025-12-30 16:27

composer怎么配置自动化代码风格检查_composer引入php-cs-fixer【教程】

2025-12-30 16:28

Mac的iCloud云盘如何使用？（文件同步与管理）

2025-12-30 16:30

如何通过Composer安装PHP-CS-Fixer并配置脚本_使用Composer统一团队代码风格

2025-12-30 16:38

热门AI工具

DeepSeek

幻方量化公司旗下的开源大模型平台

AI大模型

开放平台

豆包大模型

字节跳动自主研发的一系列大型语言模型

AI大模型

通义千问

阿里巴巴推出的全能AI助手

AI大模型

腾讯元宝

腾讯混元平台推出的AI助手

文档处理

Excel 表格

文心一言

文心一言是百度开发的AI聊天机器人，通过对话可以生成各种形式的内容。

AI大模型

中文写作

讯飞写作

基于讯飞星火大模型的AI写作工具，可以快速生成新闻稿件、品宣文案、工作总结、心得体会等各种文文稿

中文写作

写作工具

即梦AI

一站式AI创作平台，免费AI图片和视频生成。

图片拼接

图画生成

ChatGPT

最最强大的AI聊天机器人程序，ChatGPT不单是聊天机器人，还能进行撰写邮件、视频脚本、文案、翻译、代码等任务。

AI大模型

中文写作

智谱清言 - 免费全能的AI助手

AI大模型

PDF 文档

相关专题

string转int

在编程中，我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算，或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章，欢迎大家前来学习阅读。

312

2023.08.02

int占多少字节

int占4个字节，意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值，在某些情况下也可能是2个字节或8个字节，int是一种常用的数据类型，用于表示整数，需要根据具体情况选择合适的数据类型，以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容，供大家免费下载体验。

522

2024.08.29