链式前向星

在存储图的时候，一般有三种办法：

1. 邻接矩阵
2. 邻接表
3. 链式前向星

今天就大概来讲一讲这三种方法

邻接矩阵

邻接矩阵是这三种方法中最直观的方法了，大概意思就是生成一个二维数组。并且将数组中的每一个值都初始化为 -1 ，然后再将数据存入二维数组中

例如：

现有如下一组边

(起点，终点，边长度)
(1,2,3)
(1,4,4)
(1,3,1)
(2,5,2)
(4,5,5)
(3,5,6)

那么在这个二维数组中，（假如二维数组叫做 w ），就有边的长度为 w[1] [2] = 3, w[1] [4] = 4 ... 以此类推

这样的存储方式虽然简单易写，但是空间复杂度却很高，因此人们开发出了第二种方式

邻接表

相较于邻接数组，邻接表的空间复杂度更低，其原理大概是这样

我们依旧使用上表数据，可以知道，边的起点有1,2,3,4 四种，

我们首先看1：

1先是能到2，并且长度为3，所以我们先画出这样一个节点

这样就表示1 => 2 ，权值（长度）为3

同理，1 => 3 就这样表示

那么起点为1的这一系列边我们怎么表示呢？

对于起点为2的，也是这样表示

其余同理

但是这样写的话就太过复杂了，有没有简单的方法呢？

链式前向星

前向星我就不讲了，反正也没人傻到去用那个100%超时的玩意儿

链式前向星其实就是邻接表的简化版本，其本质是一样的

首先我们需要一个结构体来存储边信息

struct node{
    int to;    // 终点（不是链表末尾的那个点，别误会了）
    int w;    // 边长
    int next;    // 下一个点
}Edge[MAXN];
int cnt = 0, Head[MAXN];    // head 用于记录起始点

同时，有了结构体，也得要存数据吧，

void AddEdge(int bg, int ed, int weight)
{
    Edge[cnt].to = ed;
    Edge[cnt].w = weight;
    Edge[cnt].next = Head[bg];
    Head[bg] = cnt++
}

使用AddEdge函数就可以添加一个新的边（单向）了

注意：AddEdge是将数据添加到链表的最前面