SaroProck ⚡
【数据结构】邻接表与链式前向星

【数据结构】邻接表与链式前向星

Fri Jun 16 2023
4 minutes
技术 OI学习笔记 数据结构 邻接表 链式前向星 数据结构 图论 O2 cpp OI
531 words

邻接表与链式前向星更正： 使用vector存图的叫做邻接表 使用数组模拟的叫做链式前向星

邻接表（使用 vector）#

使用邻接表的优劣： 优势：

  1. 码量少，易操作
  2. 不用担心空间，不易写错

劣势：

  1. cpp11 之前不能使用auto v : i形式遍历 vector
  2. 在不能开启O2的题目中较慢（POJ 全占）

存图方式#

CPP
1
2
3
4
5
6
7
8
9
10
11
12
struct line // 自定义结构体
{
    int ver; // 指向的结点
    int edge; // 边的权值
    line(int v, int e) // 构造函数
    {
        ver = v;
        edge = e;
    }
};

vector<line> g[MAX]; // 新建邻接表

遍历方式#

对于 C++11 后的 OJ，使用如下方式遍历：

CPP
1
2
3
4
5
6
7
// line是结构体的名字
// from是父节点的下标
for(line son : g[crd])
{
    // 示例代码，含义为不经过父节点
    if(son.ver == from) continue;
}

对于 C++11 前的 OJ，使用如下方式遍历

其实这里建议使用链式前向星，因为不支持 C++11 的 OJ 很可能没有 O2

CPP
1
2
3
// line是结构体名字
for (line son = g.begin(); son != g.end(); son++)
// 下略……

添加方式#

CPP
1
2
3
4
5
6
7
8
// 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));
}

链式前向星#

使用链式前向星的优劣： 优势：

  1. 速度快，无需O2
  2. 不受 C++版本限制，适用于所有题目

劣势：

  1. 数组模拟链表，初学者不易理解
  2. 码量多，不理解容易打错，不易 Debug

存图方式#

CPP
1
2
3
4
5
6
7
struct line
{
    int ver; // 指向的结点
    int next; // 下一条边
    // int edge; // 边的权值
}node[MAX * 2]; // 新建链式前向星
int head[MAX]; // 表头数组

遍历方式#

CPP
1
2
for(int son = head[crd]; son; son = node[son].next)
// 下略……

添加方式#

CPP
1
2
3
4
5
6
7
8
9
// 前向星添加边（使用函数）
// 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;
}