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

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

邻接表（使用vector）

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

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

劣势：

1. C++11之前不能使用auto v : i形式遍历vector
2. 在不能开启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));
}

---

链式前向星

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

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

劣势：

1. 数组模拟链表，初学者不易理解
2. 码量多，不理解容易打错，不易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;
}