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

发布于:2025-03-18 ⋅ 阅读:(19) ⋅ 点赞:(0)

在 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 实现带权图的高效存储。


在这里插入图片描述


网站公告

今日签到

点亮在社区的每一天
去签到