图论算法在信息学竞赛中有着非常广泛的应用, 也频繁在考试与比赛中作为重要的考察知识.本文汇总并分类了信息学竞赛中的图论算法.
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])
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<e[x].size();++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]<dfn[x]&&y!=fa) {
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<e[x].size();++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]<delta)delta=d[i],tmp=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;
}