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

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


邻接表与链式前向星更正: 使用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;
}