基础图论算法

简单的图论算法,涉及存图 , 最短路 ,

存图

图论的第一步

邻接矩阵

朴素的存图方式 , 用于 Floyd , 稠密图 , 拓扑排序 .

实现

使用二维数组$E[i][j]$ , $E[i][j]=0$表示无法$i \rightarrow j$ , 再用$E[i][j]$记录边权/边数等数据.

前向星

使用最广泛的存稀疏图方式

向量数组 (Vector)

使用Vector代替前向星的链表.

优/劣势

既能在控制空间复杂度的前提下快速遍历边 , 也有顺序表的某些优势 (易于排序) . 但使用STL略微增加了时间复杂度 .

最短路算法

图论的第一类算法

朴素的迪杰斯特拉(Dijkstra)

使用

迪杰斯特拉(Dijkstra)的堆优化

关键操作为有序的松弛 , 使用优先队列(priority_queue) 即小根堆(pile) 进行优化 . 最稳定的 $nlogn$ 算法 , 但无法处理含负权边的图 .

适用范围

边权非负 (原因见下 正确性证明)

思路/时间复杂度分析

从源点开始拓展节点 , 使用 $vis[i]$ 记录节点 $i$ 是否已经拓展 , 以 $d[i]$ 为拓展顺序的标准 , 先拓展 $d[i]$ 小的 (使用小根堆完成) . 这样每个节点只需拓展一次 , 设节点数为 $n$ , 边数为 $m$ . 则时间复杂度为 $O(nlogm + mlogm)$ , 其中 $nlogm$ 是每次从小根堆中取拓展节点的时间 , $mlogm$ 是最坏需要向小根堆中加入 $m$ 次节点 .

正确性证明——为什么每个节点只会拓展一次

当节点 $i$ 拓展完毕后 , $vis[i]=1$ , 此时记 $d[i]=d$ , 之后再拿出来拓展的节点 $j$ 一定有 $d[j] \ge d$ , 又因为边权非负 , 则 $d[j] + e[i].val \ge d $ , 则 $i$ 一定不会被之后的点更新 .

核心代码

使用优先队列优化

struct Edge{
    int next,to,w;
};
struct Node{
    int x,val;
    bool operator < (const Node &n)const{
        return val>n.val;
    }
};
/////////
int d[maxn];
bool vis[maxn];
priority_queue<Node> pq;

void dij(int s){
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    d[s]=0;pq.push((Node){s,0});
    while(!pq.empty()){
        int i;
        Node N=pq.top();pq.pop();
        int x=N.x;
        if(vis[x])continue;
        vis[x]=true;
        for(i=head[x];i;i=e[i].next){
            int to=e[i].to;
            if(!vis[to] && d[to]>d[x]+e[i].w){
                d[to]=d[x]+e[i].w;
                pq.push((Node){to,d[to]});
            }
        }
    }
}
//////////////

Bellman-Ford

SPFA (Shortest Path Faster Algorithm)

正如其名 , 快速的最短路算法 , 在随机数据上有很好的表现 , 面对菊花图等会退化 . 是上文所说的Bellman的优化算法 . 码量相比 Dij 要少 也是算法竞赛中SPFA的唯二优势

核心代码

Floyd-Warshall

运用dp (刷表) 思想的算法 , 用于求任两点之间的最短路 , 还可用于 传递闭包(Transitive closure)

核心代码

for(int k=1;k<=n;k++)//中转点在最外层
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

正确性证明

简洁的后果是他的证明很难理解 .