【数据结构】邻接表与链式前向星
...
周五 6月 16 2023
---
499 字 · 3 分钟
邻接表与链式前向星更正： 使用
vector存图的叫做邻接表使用数组模拟的叫做链式前向星
邻接表（使用 vector）
使用邻接表的优劣： 优势：
- 码量少，易操作
- 不用担心空间，不易写错
劣势：
- cpp11 之前不能使用
auto v : i形式遍历 vector- 在不能开启
O2的题目中较慢（POJ 全占）
存图方式
struct line // 自定义结构体
{
int ver; // 指向的结点
int edge; // 边的权值
line(int v, int e) // 构造函数
{
ver = v;
edge = e;
}
};
vector<line> g[MAX]; // 新建邻接表遍历方式
对于 C++11 后的 OJ，使用如下方式遍历：
// line是结构体的名字
// from是父节点的下标
for(line son : g[crd])
{
// 示例代码，含义为不经过父节点
if(son.ver == from) continue;
}对于 C++11 前的 OJ，使用如下方式遍历
其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2
// line是结构体名字
for (line son = g.begin(); son != g.end(); son++)
// 下略……添加方式
// N为边的数量
for(int i = 1; i < N; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].push_back(line(v, w));
g[v].push_back(line(u, w));
}链式前向星
使用链式前向星的优劣： 优势：
- 速度快，无需
O2- 不受 C++版本限制，适用于所有题目
劣势：
- 数组模拟链表，初学者不易理解
- 码量多，不理解容易打错，不易 Debug
存图方式
struct line
{
int ver; // 指向的结点
int next; // 下一条边
// int edge; // 边的权值
}node[MAX * 2]; // 新建链式前向星
int head[MAX]; // 表头数组遍历方式
for(int son = head[crd]; son; son = node[son].next)
// 下略……添加方式
// 前向星添加边（使用函数）
// tot为所有边的数量，初始值为0
void add(int u, int v/*, int edge*/)
{
node[++tot].next = head[u];
node[tot].ver = v;
//node[tot].edge = edge;
head[u] = tot;
}
评论区