图论算法在信息学竞赛中有着非常广泛的应用, 也频繁在考试与比赛中作为重要的考察知识.本文汇总并分类了信息学竞赛中的图论算法.
1 生成树与最短路
1.1 Prim 算法
Prim 算法可以求出一张图的最小生成树, 时间复杂度为 \(\mathcal{O}((|V|+|E|)\log |V|)\).
memset(dis,0x3f,sizeof(dis));
dis[1] = 0;
q.push({1,0});
while(!q.empty()) {
if(cnt>=n)break;
int x=q.top().x,d=q.top().d;
q.pop();
if(vis[u])continue;
vis[u]=1;
++cnt;
res+=d;
for(auto to:e[x]){
int y=to.to,w=to.w;
if(w dis[v]=w,q.push({v,w}); } } 1.2 Kruskal 算法 Kruskal 算法可以求出一张图的最小生成树, 时间复杂度为 \(\mathcal{O}(|E|\log |E|)\). sort(e+1,e+m+1,cmp); int ans=0,cnt=0; for(int i=1;i<=m;++i){ int x=e[i].u,y=e[i].v,z=e[i].w; int fx=fd(x),fy=fd(y); if(fx==fy)continue; fa[fx]=fy; ans+=z,cnt++; if(cnt==n-1)break; } 1.3 Dijkstra 算法 Dijkstra 是一种效率优秀的单元最短路算法, 但不能处理负边权. 时间复杂度为 \(\mathcal{O}(|E|\log |E|)\). memset(d,0x3f,sizeof(dis)); dis[s]=0; q.push({s, 0}); while(!q.empty()){ int x=q.top().x; q.pop(); if(vis[x])continue; vis[x]=1; for(auto to:e[x]){ int y=to.to,w=to.w; if(!vis[y]&&d[y]>d[x]+w){ d[y]=d[x]+w; q.push({x,d[x]}); } } } 1.4 SPFA 算法 SPFA 可以用于处理存在负边权的最短路问题, 也可以处理最长路问题. SPFA 算法也被常用于对于一个图中负环存在的判定. 最劣时间复杂度为 \(\mathcal{O}(|V||E|)\), 但通常情况下效率较高. memset(dis,0xff,sizeof(dis)); dis[s]=0,vis[s]=cnt[s]=1; q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); vis[x]=0; for(auto to:e[x]){ int y=to.to,w=to.w; if(dis[y]>dis[x]+w){ dis[y]=dis[x]+w; if(!vis[y]){ q.push(y); cnt[y]++; vis[y]=1; if(cnt[y]>n+1)/* 存在负环 */; } } } } 2 连通性算法 2.1 强联通分量 Tarjan 算法可以用于求有向图的强联通分量 (SCC). 时间复杂度为 \(\mathcal{O}(|V|+|E|)\). void tarjan(int x) { ++_time; dfn[x]=low[x]=_time; st.push(x); vis[x]=1; for(int y:e[x]) if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(vis[y]) low[x]=min(low[x],dfn[y]); if(dfn[x]==low[x]){ v[x]=0; ++num; id[x]=num; sz[num]=1; while(st.top()!=x){ int t=st.top(); st.pop(); v[t]=0; id[t]=num; sz[num]++; } st.pop(); } } 2.2 点双联通分量 Tarjan 算法可以求出无向图的点双联通分量. 时间复杂度为 \(mathcal{O}(|V|+|E|)\). void tarjan(int x,int fa) { dfn[x]=low[x]=++_time; int siz=0; s[++top]=x; for(int y:e[x]) if(!dfn[y]){ siz++; tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ cnt++; while(s[top+1]!=y)ans[cnt].push_back(s[top--]); ans[cnt].push_back(x); } } else if(y!=fa)low[x]=min(low[x],dfn[y]); if(!siz&&x==rt) ans[++cnt].push_back(x); } 2.3 割点 Tarjan 算法可以求出无向图的割点. 时间复杂度为 \(\mathcal{O}(|V|+|E|)\). void tarjan(int x,int fa) { int son=0; dfn[x]=low[x]=++tot; for(int i=0;i { int y=e[x][i]; if(y==fa)continue; if(!dfn[y]) { son++; tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]&&fa)cnt+=!b[x],b[x]=1; } else low[x]=min(low[x],dfn[y]); } if(son>=2&&fa==0)cnt+=!b[x],b[x]=1; } 2.4 边双联通分量 Tarjan 算法可以求出无向图的边双联通分量, 时间复杂度为 \(\mathcal{O}(|V|+|E|)\). void tarjan(int x,int edg){ dfn[x]=low[x]=++_time; for (int i=hd[x];i;i=nxt[i]) { int y=to[i]; if(!dfn[y]){ tarjan(y,i); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]) bridge[i]=bridge[i^1]=1; } else if(i!=(edg^1)) low[x]=min(low[x],dfn[y]); } } void dfs(int x) { col[x]=dcc; if(x) ans[dcc].push_back(x); for(int i=hd[x];i;i=nxt[i]) { int y=to[i]; if (col[y]||bridge[i])continue; dfs(y); } } 2.5 割边 Tarjan 算法可以求出无向图的割边, 时间复杂度为 \(\mathcal{O}(|V|+|E|)\). void tarjan(int x,int fa) { fat[x]=fa; dfn[x]=low[x]=++_time; for(int y:e[x]){ if(!dfn[v]){ tarjan(y,x); low[x]=min(low[x],low[y]); if(low[y]>dfn[x]){ bridge[y] = true; ++cnt; } }else if(dfn[y] low[u] = min(low[u], dfn[v]); } } } 2.6 圆方树 3 二分图 3.1 二分图最大匹配 Hungary 算法通常用来解决二分图的最大匹配问题. 时间复杂度为 \(\mathcal{O}(|V||E|)\). bool dfs(int x,int tag){ if(v[x]==tag)return 0; v[x]=tag; for(int i=0;i int y=e[x][i]; if(!mat[y]||dfs(mat[y],tag)){ mat[y]=x; return 1; } } return 0; } 3.2 二分图最大权完美匹配 KM 算法用于解决二分图最大权匹配. 时间复杂度为 \(\mathcal{O}(|V|^3)\). void bfs(int s){ int x,y,delta,tmp=0; y=0; memset(pre,0,sizeof(pre)); for(int i=1;i<=n;++i)d[i]=1e18; mat[y]=s; while(1){ x=mat[y];delta=1e18;visy[y]=1; for(int i=1;i<=n;++i){ if(visy[i])continue; if(d[i]>la[x]+lb[i]-e[x][i]){ d[i]=la[x]+lb[i]-e[x][i]; pre[i]=y; } if(d[i] } for(int i=0;i<=n;++i){ if(visy[i])la[mat[i]]-=delta,lb[i]+=delta; else d[i]-=delta; } y=tmp; if(mat[y]==-1)break; } while(y)mat[y]=mat[pre[y]],y=pre[y]; } int KM(){ memset(mat,0xff,sizeof(mat)); memset(la,0,sizeof(la)); memset(lb,0,sizeof(lb)); for(int i=1;i<=n;++i){ memset(visy,0,sizeof(visy)); bfs(i); } int res=0; for(int i=1;i<=n;++i){ if(mat[i]!=-1)res+=e[mat[i]][i]; } return res; }