bro高一才开始自学图论

图的存储

建议无脑用链式前向星

0x01. 什么是链式前向星

定义(摘自OI wiki)

本质上是用链表实现的邻接表

具体来说：

以有向边的形式 ，\(head\) 数组存当前边的编号，\(e[i].nxt\) 数组存上一次加的以 \(u\) 为起点的边的编号，这样就能实现用 \(head[u]\) 和 \(e[i].nxt\) 遍历所有出边；\(v\) 存边的终点； \(w\) 存边权

加边操作：

void add (int u, int v, int w) {
    e[++tot].nxt = head[u]; 
    e[tot].v = v; 
    e[tot].w = w;
    head[u] = tot;      
}

找是否存在 \(u\) 到 \(v\) 的边：

bool find(int u, int v) {
    for(int i = head[u]; i; i = e[i].nxt) { 
        if (e[i].v == v) {
          return true;
        }
    }
    return false;
}

遍历一个节点连向的所有出边：

for(int i = head[u]; i; i = e[i].nxt){
    int v = e[i].v, w = e[i].w;
    ...
}

遍历图：

void dfs(int u) {
    if(vis[u]) return;
    vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt) {
        ...
        dfs(e[i].v);
    }
}

0x02. 性质与复杂度

·可以通过每次多存一条反边来存储树或无向图，复杂度 \(O(m)\)
·可以查询是否存在 \(u\) 到 \(v\) 的边，复杂度 \(O(u)\)
·可以遍历点 \(u\) 的所有出边，复杂度 \(O(u)\)
·可以遍历整张图，复杂度 \(O(n+m)\)
·空间复杂度 \(O(m)\)

任意点对最短路: Floyd 算法

可检测负环单源最短路: Bellman–Ford 算法(以及SPFA)

非负权图单源最短路: Dijkstra 算法

任意点对最短路：Johnson 算法