有向图、无向图

建图

链式前向星

struct Edge {
    int to, w, next;
} edge[MAX_EDGE];

int head[MAX_NODE], cnt = 0; // cnt用于给边编号，从0开始

void addEdge(int u, int v, int w) {
    edge[cnt].to = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u]; // 新边指向原来的第一条边
    head[u] = cnt++;          // 更新头结点，指向新边
}

for (int i = head[u]; i != -1; i = edge[i].next) {
    int v = edge[i].to;
    int w = edge[i].w;
    // 处理从u到v的这条边...
}

head 数组通常初始化为 -1，边遍历的结束条件为 i != -1。也有实现将其初始化为 0，此时边编号从 1 开始，遍历结束条件为 i != 0

存储无向图时，需要添加两条有向边（正向和反向），因此 edge 数组的大小需要是边数的两倍。此时，可以通过 i ^ 1 的异或运算快速找到一条边的反向边。

vector

vector<int> g[N];

g[x].push_back(y);

for(auto v:g[u]) {
    cout << v;
}

最短路

Dijkstra

SPFA

Floyd

求：任意两点间最短路

解：矩阵乘法中+换为min

树

定义: n个点，n-1条边，联通

入度、出度