存图

图的表达方式有多种
设n为点数，m为边数。

邻接矩阵

用二维数组来存图，存储空间O(n^2)。
G[u][v]表示存在一条从u指向v的边。

邻接表

链式存图。
链表，vector。多用vector

边集存图

边集数组存图。结构体包装起点、终点、权值等信息。
但用数组存完这些杂乱无章的边之后，一般都会对其排个序。

前向星

前向星是在读入边的信息后，对边集数组中的边按照起点顺序排序(可用基数排序更快)。
这样起点相同的边就可以在数组进行连续访问了。

链式前向星

链式前向星和邻接表类似，只是用数组代替结点了。有两个数组变量: head[], Edge[].
Edge是struct变量

typedef struct edge{
    int from,to,weight;
    int next;
}edge;

head[i]表示i结点所连的第一条边的下标，第二条边的下标是第一条边的next，依次类推，直至next取值为inf，表示没有边了。
每次插入新的边的时候，是插在表头的，这样能做到O(1)插入新边。

void AddEdge(int from,int to,int weight){
    tot++;
    e[tot].from = from;
    e[tot].to = to;
    e[tot].weight = weight;
    e[tot].next = head[from];
    head[from] = tot;
}

链式前向星效果很好，空间上没有浪费，时间上也是最优，比vector快(因为vector要push，可能会有很大时间开销)。