邻接表用vector存储无向图，addEdge双向添加边，print遍历输出；带权图用vector存边权，适合稀疏图，空间省、遍历快。
在C++中实现图的邻接表表示，是一种高效且常用的方式，尤其适合稀疏图（边数远小于顶点数平方）的存储和操作。邻接表使用数组或vector配合链表（或vector）来存储每个顶点的邻接顶点，既能节省空间，又能方便地遍历邻居节点。
邻接表的基本结构
一个无向图或有向图可以用以下方式建模：
用一个vector> 来表示每个顶点连接的其他顶点。 如果是带权图，可以用 vectorair>>，其中 pair 的第一个值是邻接点，第二个是边的权重。 顶点编号通常从0或1开始。
基础实现：无向无权图
// graph_adjacency_list.cpp
#include iostream>
#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 print() const {
for (int i = 0; i cout for (int neighbor : adj[i]) {
cout }
cout }
}
};
// 使用示例
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 或自定义结构体。
立即学习“C++免费学习笔记（深入）”；
class WeightedGraph {
private:
int V;
vector>> 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 cout for (auto& edge : adj[i]) {
cout }
cout }
}
};
关键点说明
使用 vector> 是最常见做法，动态扩容，代码简洁。 对于稀疏图，邻接表比邻接矩阵更节省内存。 遍历某个顶点的所有邻居时间复杂度为 O(度)，效率高。 若频繁查询两点是否有边，可考虑搭配哈希表优化，但一般DFS/BFS不需要。 支持快速插入边，删除边稍麻烦（需在vector中erase），如需频繁删除可用 list 替代 inner vector。基本上就这些。这种实现方式灵活、直观，是算法题和实际开发中图结构的标准写法之一。
以上就是c++++ 图的邻接表表示 c++图数据结构实现的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1486594.html
微信扫一扫 
支付宝扫一扫 
