c++图论(二)之图的存储图解

server/2025/3/18 20:02:40/

在 C++ 中实现图的存储时,常用的方法包括 邻接矩阵(Adjacency Matrix)邻接表(Adjacency List)边列表(Edge List)。以下是具体实现方法、优缺点分析及代码示例:


1. 邻接矩阵(Adjacency Matrix)

原理
  • 使用二维数组 matrix[u][v] 表示顶点 uv 的连接关系。
  • 适用于 稠密图(边数接近顶点数的平方)。
  • 无权图matrix[u][v] = 1 表示存在边;0 表示无连接。
  • 带权图matrix[u][v] = weight 表示边的权重。
图解

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

C++ 实现
#include <vector>
using namespace std;// 定义图的顶点数
const int V = 100;// 无权图的邻接矩阵
vector<vector<int>> adjMatrix(V, vector<int>(V, 0));// 添加无向边
void addUndirectedEdge(int u, int v) {adjMatrix[u][v] = 1;adjMatrix[v][u] = 1;
}// 添加带权有向边
void addDirectedWeightedEdge(int u, int v, int weight) {adjMatrix[u][v] = weight;
}// 检查边是否存在
bool hasEdge(int u, int v) {return adjMatrix[u][v] != 0;
}
优点
  • 快速判断两顶点是否相邻:时间复杂度 O(1)。
  • 适合频繁查询边的存在性
缺点
  • 空间复杂度高:O(V²),不适合顶点数多(如 V > 1e4)的稀疏图。
  • 插入/删除边效率低:需要修改二维数组。

2. 邻接表(Adjacency List)

原理
  • 为每个顶点维护一个链表或动态数组,存储其邻接顶点。
  • 适用于 稀疏图(边数远小于顶点数的平方)。
  • 无权图adjList[u] 存储 v 的集合。
  • 带权图adjList[u] 存储 pair<v, weight>
C++ 实现
#include <vector>
#include <list>
using namespace std;// 无权图的邻接表(使用 vector)
vector<vector<int>> adjList;// 初始化顶点数为 n 的图
void initGraph(int n) {adjList.resize(n);
}// 添加无向边
void addUndirectedEdge(int u, int v) {adjList[u].push_back(v);adjList[v].push_back(u);
}// 带权图的邻接表(使用 vector<pair>)
vector<vector<pair<int, int>>> weightedAdjList;// 添加带权有向边
void addWeightedDirectedEdge(int u, int v, int weight) {weightedAdjList[u].emplace_back(v, weight); // C++11 的 emplace_back 更高效
}// 遍历顶点 u 的邻居
void traverseNeighbors(int u) {for (const auto& neighbor : adjList[u]) {// 处理邻居顶点 neighbor}
}
优点
  • 空间复杂度低:O(V + E),适合大规模稀疏图。
  • 高效遍历邻接顶点:时间复杂度与邻接顶点数成正比。
缺点
  • 查询边的存在性慢:需要遍历邻接表,时间复杂度 O(degree(u))。

3. 边列表(Edge List)

原理
  • 将图的边存储为 (u, v, weight) 的列表。
  • 适用于需要 按边遍历 的场景(如 Kruskal 算法求最小生成树)。
C++ 实现
#include <vector>
using namespace std;// 定义边的结构体
struct Edge {int u, v, weight;Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
};vector<Edge> edgeList;// 添加带权边
void addEdge(int u, int v, int weight) {edgeList.emplace_back(u, v, weight);
}// 遍历所有边
void traverseEdges() {for (const Edge& e : edgeList) {// 处理边 e.u -> e.v,权重 e.weight}
}
优点
  • 存储简单:适用于算法需要全局遍历边(如 Kruskal 算法)。
  • 节省空间:仅存储存在的边,空间复杂度 O(E)。
缺点
  • 查询顶点邻接关系慢:需要遍历整个边列表。

4. 链式前向星(Linked Forward Star)

原理
  • 一种紧凑的邻接表实现,通过数组模拟链表,常用于算法竞赛。
  • 使用三个数组:head[]to[]next[]weight[]
C++ 实现
const int MAX_EDGES = 1e5; // 最大边数
int head[MAX_EDGES];       // head[u] 表示顶点 u 的第一条边的索引
int to[MAX_EDGES];         // 存储边的终点
int next[MAX_EDGES];       // 存储下一条边的索引
int weight[MAX_EDGES];     // 存储边的权重
int edgeCount = 0;         // 当前边数// 初始化
void init() {memset(head, -1, sizeof(head)); // 初始化为 -1
}// 添加有向边 u -> v,权重 w
void addEdge(int u, int v, int w) {to[edgeCount] = v;weight[edgeCount] = w;next[edgeCount] = head[u];head[u] = edgeCount++;
}// 遍历顶点 u 的邻接边
void traverseEdges(int u) {for (int i = head[u]; i != -1; i = next[i]) {int v = to[i];int w = weight[i];// 处理边 u -> v,权重 w}
}
优点
  • 内存紧凑:适合处理超大规模图(如顶点数 1e5 以上)。
  • 高效遍历:与邻接表性能接近。
缺点
  • 实现复杂:需要手动管理数组索引。

5. 存储方法对比及适用场景

存储方法时间复杂度(查询边)空间复杂度适用场景
邻接矩阵O(1)O(V²)稠密图、频繁查询边的存在性
邻接表O(degree(u))O(V + E)稀疏图、频繁遍历邻接顶点
边列表O(E)O(E)需要全局遍历边的算法
链式前向星O(degree(u))O(V + E)算法竞赛中的大规模图处理

6. 动态图的存储优化

  • 邻接表的动态扩展:使用 vectorpush_back 动态添加边。
  • 删除边的优化:使用链表(如 list)或标记法(惰性删除)。

总结

  • 邻接矩阵:适合稠密图,快速查询边的存在性。
  • 邻接表:适合稀疏图,高效遍历邻接顶点(推荐使用 vector<vector<pair<int, int>>>)。
  • 边列表:适合需要全局处理边的场景(如 Kruskal 算法)。
  • 链式前向星:适合算法竞赛中的高性能需求。

代码建议:大多数情况下优先使用 邻接表,结合 C++ 的 vectorpair 实现带权图的高效存储。


在这里插入图片描述


http://www.ppmy.cn/server/176040.html

相关文章

双 Token 无感刷新机制在前后端分离架构中实现

在前后端分离的架构中&#xff0c;双 Token 无感刷新是一种常见的身份验证机制&#xff0c;用于在 Access Token 过期时&#xff0c;通过 Refresh Token 自动获取新的 Access Token&#xff0c;从而避免用户频繁登录。 1. 双 Token 无感刷新的核心流程 1.1 核心流程 用户登录&…

ElementUI 表格中插入图片缩略图,鼠标悬停显示大图

如何在 ElementUI 的表格组件 Table 中插入图片缩略图&#xff0c;通过鼠标悬停显示大图&#xff1f;介绍以下2种方式&#xff1a; 方法1&#xff1a;直接在模板元素中插入 <template><el-table :data"tableData"><el-table-column label"图片…

conda创建Python虚拟环境的原理

<Conda>在创建Python虚拟环境时&#xff0c;其背后的原理涉及到Conda包的版本管理和隔离。Conda是一个开源的包管理器和环境管理系统&#xff0c;它主要用于安装、运行和部署各种Python、R、Ruby、Node.js等语言的包、依赖和库。以下是创建Python虚拟环境的原理&#xff…

使用 Docker 部署前端项目全攻略

文章目录 1. Docker 基础概念1.1 核心组件1.2 Docker 工作流程 2. 环境准备2.1 安装 Docker2.2 验证安装 3. 项目配置3.1 项目结构3.2 创建 Dockerfile 4. 构建与运行4.1 构建镜像4.2 运行容器4.3 访问应用 5. 使用 Docker Compose5.1 创建 docker-compose.yml5.2 启动服务5.3 …

电脑如何录屏

以下是电脑录屏的常用方法总结&#xff0c;涵盖系统自带工具、第三方软件及进阶功能&#xff0c;结合不同场景需求推荐最佳方案&#xff1a; 一、系统自带工具 Xbox Game Bar&#xff08;Windows 10/11&#xff09; 操作步骤&#xff1a;按 WinG 打开游戏栏 → 点击录制按钮&am…

JVM调优关注的核心指标?

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…

RabbitMQ 基本原理详解

1. 引言 在现代分布式系统中&#xff0c;消息队列&#xff08;Message Queue&#xff09;是实现异步通信、解耦系统组件、提高系统可靠性和扩展性的重要工具。RabbitMQ 作为一款开源的消息中间件&#xff0c;因其高性能、易用性和丰富的功能&#xff0c;被广泛应用于各种场景。…

Android PC 要来了?Android 16 Beta3 出现 Enable desktop experience features 选项

在之前的 《Android 桌面窗口新功能推进》 我们就聊过&#xff0c;Google 就一直在努力改进 Android 的内置桌面模式&#xff0c;例如添加了适当的窗口标题、捕捉窗口的能力、悬停选项、窗口大小调整、最小化支持、app-to-web 等。 比如在搭载 Android 15 QPR 1 Beta 2 的 Pix…