【前向星】

1. 把边集数组（储存边的数组）中的每一条边按照起点从小到大排序，如果起点相同就按照终点从小到大。（这样使得起点相等的边就能够在数组中进行连续访问）
   缺点是需要在所有边都读入完毕的情况下对所有边进行一次排序，带来了时间开销，实用性也较差。
2. 并且记录下以某个点为起点的所有边在数组中的起始位置和存储长度。
3. head[i]数组记录：以i为边集在数组中的第一个存储位置。

• 链式前向星和普通的前向星很类似，就是多了一个指向下一个的指针。
• 我们经常将链式前向星做成这种结构：

  struct EDGE {
      int u, v, w, next;//u，v为两个相邻结点，w为权值，next为指向下一条边的指针
      EDGE() {}
      void init(int u, int v, int w, int next) {
          this->u = u, this->v = v, this->w = w, this->next = next;
      }
  }edge[MAXM];

• 并且用head[i]，来表示以i为起点的第一条边存储的位置。所以我们平常会也这样存储。（所以我们也会发现，其实存进去的是最后一个输入的）：

  for (int i = 1; i <= m; i++) {
      int u, v, w; read(u); read(v); read(w);
      edge[total].init(u, v, w, );
      edge[total].init(v, u, w);
          total++;
  }

• 或者这样单列一个函数初始化：

  void add_edge(int u,int v,int w) {
          edge[cnt].w = w;
         edge[cnt].to = v;
        edge[cnt].next = head[u];
        head[u] = cnt++;
  }

• 我们可以用一个表格来理解理解

  edge[0].to = 2	edge[0].next = -1	head[1] = 0
  edge[1].to = 3	edge[1].next = -1	head[2] = 1
  edge[2].to = 4	edge[2],next = -1	head[3] = 2
  edge[3].to = 3	edge[3].next = 0	head[1] = 3
  edge[4].to = 1	edge[4].next = -1	head[4] = 4
  edge[5].to = 5	edge[5].next = 3	head[1] = 5
  edge[6].to = 5	edge[6].next = 4	head[4] = 6

struct Node {
     int to, next, w;
} edge[maxn];

• 如果一个结点的出度大于1，则其中结点编号最大的结点的next将指向结点编号次之的结点。
• 上面例子：从结点1出发，结点编号最大的是结点5，结点5的next将会是3。而结点3的next将会是结点2，而到了结点2之后结点1的所有出边都已经被处理了，所以结点2的next将会是-1。

• 简单概括来说就是对于第i条边的终点。上面例子：输入第一组边（1， 2）的时候，edge[1].to = 2（假设数组从1开始存储，这是第一组数据）。

• 我们还需要一个head数组，这个head数组和next是这个链式存储结构的关键所在！
•  那么这个head数组用来存什么呢？对于你输入的边，用来存以i为起点的边的存储位置。
• 那么如果以i为起点的边出度大于1怎么办？此时head[i]会存入在输入中最后输入的以i为起点的编号。
• 上面例子：对于结点1，它的出度为3，由先往后分别输入了（1， 2）（1， 3）（1， 5），最后存入head的就会是5（2和3其实也有被存储的时候，但是后来会被5覆盖掉），即结果就是head[1] = 5。
• 然后我们再按head来遍历，就可以把以1为起点的边全部遍历完了。