邻接矩阵

邻接矩阵：表示顶点之间相邻关系的矩阵

有权重

g[i][j]:值为权重（表示有一条从i指向j的边，边权为g[i][j]）或无穷大

无权重

g[i][j]:值为1（表示有一条从i指向j的边）或0

优缺点

优点：
    ①便于判断两个结点间是否有边
    ②便于计算各个结点的度(对于无向图，统计第i行的元素就可得到结点i的度
    对于有向图，统计第i行的元素就可得到结点i的出度，统计第i列的元素就
    可得到结点i的入度)

缺点：
    ①不便于增加和删除结点
    ②不便于统计边的数目，时间复杂度为O(n^2)
    ③空间复杂度高，O(n^2)，故邻接矩阵适用于稠密图

补：一般认为边数大于等于点数的平方的图为稠密图，反之为稀疏图

邻接表

邻接表是图的一种链式存储结构。在邻接表中，对于图中的每个结点都建立
一个单链表，把与该结点相邻接的结点放在这个单链表中。

邻接表的两种实现方式：vector、静态链表

vector

struct node{
    int id;
    int w;
};

vector<node> v[N];

//初始化
void Init(){
    for (int i = 0; i <= n; i ++ )
        v[i].clear();
}

//加边
void add(int a, int b, int c){
    node temp;
    temp.id = b;
    temp.w = c;
    v[a].push_back(temp);
}

//遍历
for (int i = 0; i < v[k].size(); i ++ ){
    int j = v[k][i].id; // 可达点
    int cost = v[k][i].w; // 权重
}

静态链表——链式前向星

链式前向星的组成成分为：边集数组、头结点数组

// 边集数组
struct Edge{
    int to;
    int next;
    int w;
} g[N];

//头结点数组
int head[N], idx;

//初始化
void Init(){
    memset(head, -1, sizeof head);
    idx = 0;
}

//头插法加边
void add(int a, int b, int c){
    g[idx].to = b;
    g[idx].w = c;
    g[idx].next = head[a];
    head[a] = idx ++ ;
}

//遍历
for (int i = head[k]; i != -1; i = g[i].next){
    int j = g[i].to;
    int cost = g[i].w;
}

注：边集数组的下标从0开始？
答：可通过与1异或运算快速得到反向边，即如果一条边的下标为i，
则它的反向边为i^1，此特性在网络流中运用非常方便。