算法模板总结——图论部分

发表于 | 分类于 | 阅读次数:
字数统计: 4,440 字

为省赛整理的常用算法模板，图论部分

最短路 Bellman-Ford 算法

松弛操作
从起始点开始对图中的每一条边进行一次松弛操作，重复这样的操作直到所有的点都达到最小的路径值

Bellman-Ford算法中判断是否有负圈

在上述算法中，最多更新V-1次就可以算出每一个结点的最短路径，如果更新超过V-1次，就说明有负圈

kuangbin模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int dist[MAXN];
struct Edge
{
    int u,v;
    int cost;
    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
bool bellman_ford(int start,int n)//点的编号从1开始
{
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[start]=0;
    for(int i=1;i<n;i++)//最多做n-1次
    {
        bool flag=false;
        for(int j=0;j<E.size();j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            int cost=E[j].cost;
            if(dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)return true;//没有负环回路
    }
    for(int j=0;j<E.size();j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;//有负环回路
    return true;//没有负环回路
}

最短路 Dijkstra 算法

将结点分成两大类，一类已经确定最短路的，一类还没有确定最短路的。每次从没有确定最短路的结点集当中取出一个‘距离’已经确定最短路的结点集中最小的点，加入。
不能够处理负边的问题，遇到负边结果出错

邻接矩阵表示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
int cost[maxn][maxn];  //邻接矩阵建图
int d[maxn];
bool used[maxn];  //表示是否被收录
int V,E;

//建图
void build()
{
	memset(d,INF,sizeof(d));
	memset(cost,INF,sizeof(cost));    //初始化邻接矩阵
	int u,v,w;
	for(int i=0;i<E;i++)
	{
        scanf("%d %d %d",&u,&v,&w);
        cost[u][v]=cost[v][u]=min(cost[v][u],w);  //去重边操作
	}
}

void dijkstra(int s)
{
    fill(d,d+V,INF);
    fill(used,used+V,false);
    d[s]=0;
    while(true)
    {
        int v=-1;
        //从未被收录的点中找出一个距离最小的点
        for(int j=0;j<V;j++)
        {
            if(!used[j]&&(v==-1||d[j]<d[v]))v=j;  //v==-1设置哨兵，确定有没有没被收录的点
        }

        if(v==-1)
            break;
        used[v]=true;
        for(int i=0;i<V;i++)
            d[i]=min(d[i],d[v]+cost[v][i]);  //松弛操作
    }
}

时间复杂度为O(V^2)

邻接链表(未验证，慎用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

 struct edge
{
    int to,cost;
};    //边属性
typedef pair<int,int> p;    //dist值扩展

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

coid dijkstra(int s)
{
    //使得堆从小到大取出值
    priority_queue<p,vector<p>,greater<p> > que;   

    fill(d,d+V,INF);
    d[s]=0;
    que.push(p(0,s));

    while(!que.empty())
    {
        p tem=que.top();  //取出dist最小的一条边
        que.pop();

        int v=tem.first;
        if(d[v]<tem.second)continue;  //之前已经更新过了
        for(int i=0;i<G[v].size();i++)
        {
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost)  //松弛操作
            {
                d[e.to]=d[v]+e.cost;
                que.push(p(d[e.to],e.to));
            }
        }
    }
}

时间复杂度就变成了：O(ElogV)

最短路 SPFA算法

链式前向星

链式前向星是一种保存图的非常好用的方法，他实际上是一个边的集合，在这个集合的基础上利用head数组来记录每个点的第一条边的信息，添加边的时候是逆序添加的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//链式前向星建图
struct Node
{
	int v,w,next;
}edges[maxm];
int head[maxn]; 

void addedge(int u,int v,int w)   //u到v的权值为w的边
{
	edges[id].v=v;
	edges[id].w=w;
	edges[id].next=head[u];    //把之前的第一条边作为当前边的最后一条边
	head[u]=id++;              //id为从0开始的标号
}

//建图
void init()
{
	memset(head,-1,sizeof(head));
	int u,v,w;
	id=0;
	for(int i=0;i<m;i++)
	{
		scanf("%d %d %d",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
}

SPFA 算法

SPFA算法实在Bellman-Ford算法的基础上加了一个队列优化，用来减少冗余的松弛操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int visit[maxn],dist[maxn];
int n,m,id;

void spfa(int st)
{
    fill(visit,visit+maxn,0);   //标记所有节点未被访问
    fill(dist,dist+maxn,INF);   //求最短路，初始化最大值
    queue<int> Q;
    visit[st]=1;
    dist[st]=0;
    Q.push(st);
    while (!Q.empty())
    {
        int now=Q.front();
        Q.pop();
        visit[now]=0;           //注意此处将该点标记为未访问
        for(int i=head[now];i!=-1;i=edges[i].next)
        {
            int v=edges[i].v;
            int w=edges[i].w;
            if(dist[v]>dist[now]+w)   //最短路松弛
            {
                dist[v]=dist[now]+w;
                if(!visit[v])
                {
                    Q.push(v);
                    visit[v]=1;
                }
            }
        }
    }
}

判断负环用SPFA

kuangbinp判断负环SPFA：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];
int cnt[MAXN];
int dist[MAXN];
bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[start]=0;
    vis[start]=true;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)return false;
                    //有负环回路
                }
            }
        }
    }
    return true;
}

多源最短路 Floyd算法

动态规划思想，不断考虑每一个结点，其状态转移方程为：

map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。

代码；

1
2
3
4
5
6
7
8
9
10
int d[MAX_V][MAX_V];
int V;

void floyd()
{
    for(int k=0;k<V;k++)
        for(int i=0;i<V;i++)
            for(int j=0;j<V;j++)
            d[i][j]=max(d[i][j],d[i][k]+d[k][j]);
}

最小生成树问题

从点出发的Prim算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int cost[maxn][maxn];
int dist[maxn];  //到已经确定的点的最短距离
bool used[maxn];
int V;

int prim()
{
    fill(dist,dist+V+1,INF);  //注意建图方式,不包括0
    fill(used,used+V+1,false);   //注意建图方式
    dist[1]=0;        //注意建图方式
    //used[0]=true;     不在这里初始初始化

    int
 res=0;

    while(true)
    {
        int v=-1;
        for(int i=1;i<=V;i++) //注意建图组织方式
        {
            //在这里对收录一号元素，因为要遍历一号元素的相邻结点
            if(!used[i]&&((v==-1)||dist[i]<dist[v]))v=i;   
        }
        if(v==-1)
            break;
        used[v]=true;
        res+=dist[v];
		//cout<<v<<" "<<res<<endl;
        for(int i=1;i<=V;i++)    //注意建图方式
            dist[i]=min(dist[i],cost[v][i]);  //不判断是否相邻
    }
    return res;
}

从边出发的Kruskal算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int pre[maxn];
int n,m;

struct edge
{
	int u,v,w;
}es[maxm];

void init()
{
	for(int i=1;i<=n;i++)
		pre[i]=i;
}

int find(int x)
{
	if(pre[x]==x) return x;
	else
		return pre[x]=find(pre[x]);
}

void unite(int x,int y)
{
	x=find(x);
	y=find(y);
	if(x==y) return;
	pre[x]=y;
}

bool comp(const edge& e1,const edge & e2)
{
	return e1.w<e2.w;
}

int Krustral()
{
	sort(es,es+m,comp);    //从小到大排序
	init();
	int ret=0;
	for(int i=0;i<m;i++)
	{
		edge e=es[i];
		if(find(e.u)!=find(e.v))
		{
			unite(e.u,e.v);
			ret+=e.w;
		}
	}
	return ret;
}

拓扑排序

给出各个节点的先后顺序，输出一个拓扑序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
int head[maxn],ip,indegree[maxn];   //indegree为入度数组，ip为边计数变量 
int n,m,seq[maxn],k;  //seq记录输出数组，k为数组中元素个数

//链式前向星建图  
struct note  
{  
    int v,next;  
} edge[maxn*maxn];  
  
void init()  
{  
    memset(head,-1,sizeof(head));  
    ip=0;  
}  
  
void addedge(int u,int v)  
{  
    edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;  
}  
  
int topo()///拓扑，可做模板  
{  
    priority_queue<int>q;         //如果结果需要排序，则使用优先队列先进行排序
    int indeg[maxn];  
    for(int i=1; i<=n; i++)       //注意是否包括0点
    {  
        indeg[i]=indegree[i];  
        if(indeg[i]==0)  
            q.push(i);  
    }  
    k=0;  
    bool res=false;  
    while(!q.empty())        //维护入度为0的数组
    {  
        if(q.size()!=1)res=true;  
        int u=q.top();  
        q.pop();  
        seq[k++]=u;  
        for(int i=head[u]; i!=-1; i=edge[i].next)  
        {  
            int v=edge[i].v;  
            indeg[v]--;  
            if(indeg[v]==0)  
                q.push(v);  
        }  
    }  
    if(k<n)return -1;///存在有向环，总之不能进行拓扑排序  
    if(res)return 0;///可以进行拓扑排序，并且只有唯一一种方式，seq数组即是排序完好的序列  
    return 1;///可以进行拓扑排序，有多种情况，seq数组是其中一种序列(排序好的)  
}  

//建图
void build()    //写在主函数里面
{
    memset(indegree,0,sizeof(indegree));
    scanf("%d %d",&n,&m);
    int _u,_v;
    init();
    for(int i=0;i<m;i++)
    {
        scanf("%d %d",&_u,&_v);
        indegree[_v]++;
        addedge(_u,_v);
    }
}

最小树型图——朱刘算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
struct edge
{
    int u,v;
    double  w;
    edge(int uu,int vv, double ww):u(uu),v(vv),w(ww){}
};

vector<edge> g;

int id[maxn],pre[maxn],v[maxn];
double inw[maxn],ans;
int n,m;
int xx[maxn],yy[maxn];

double getdis(int a,int b)
{
    double ret= sqrt(double((yy[b]-yy[a])*(yy[b]-yy[a])+(xx[b]-xx[a])*(xx[b]-xx[a])));
    return ret;
}

bool fun(int s)      //存在最小树型图时，返回TRUE，ans；不存在的时候，返回FALSE
{
    ans=0;
    while (true)
    {

        for(int i=0;i<=n;i++)
        {
            inw[i]=INF;
            id[i]=-1;
            v[i]=-1;
            pre[i]=-1;
        }
        //找到每个点的最小入边
        for(int i=0;i<g.size();i++)
            if(g[i].w <=inw[g[i].v] && g[i].v!=g[i].u)
            {
                inw[g[i].v]=g[i].w;
                pre[g[i].v]=g[i].u;
            }
        pre[s]=s;
        inw[s]=0;       //根节点没有入边
        //计算总的权重和
        for(int i=1;i<=n;i++)
        {
            if(inw[i]==INF)
                return false;     //没有找到最小的入边的时候，返回错误
            ans+=inw[i];
        }
        //判断有没有环
        int idx=1;
        for(int i=1;i<=n;i++)
        {
            if(v[i]==-1)     //v[]作用是判断有没有环
            {
                int t=i;
                while (v[t]==-1)
                {
                    v[t]=i;
                    t=pre[t];
                }
                if(v[t]!=i || t==s)
                    continue;      //没有环的时候
                id[t]=idx++;      //重构图中新的点
                for(int j=pre[t];j!=t;j=pre[j])id[j]=idx-1;     //缩点操作，确定前后点的关系
            }
        }
        if(idx==1)
            return true;
        //为不在环中的点建立图之间点的关系
        for(int i=1;i<=n;i++)
            if(id[i]==-1)id[i]=idx++;
        //重新构图,改变边连接的两个点的关系
        for(int i=0;i<g.size();i++)
        {
            g[i].w-=inw[g[i].v];
            g[i].u=id[g[i].u];
            g[i].v=id[g[i].v];
        }
        n=idx-1;
        s=id[s];
    }
}

二分图的匹配问题（匈牙利算法）

给出一个二分图，求出这个二分图的最大匹配数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/* ************************************************************************** 
//二分图匹配（匈牙利算法的DFS实现） 
//初始化：g[][]两边顶点的划分情况 
//建立g[i][j]表示i->j的有向边就可以了，是左边向右边的匹配 
//g没有边相连则初始化为0 
//L是匹配左边的顶点数，R是匹配右边的顶点数 
//调用：res=hungary();输出最大匹配数 
//优点：适用于稠密图，DFS找增广路，实现简洁易于理解 
//时间复杂度:O(VE) 
// ***************************************************************************/  
//顶点编号从1开始的  
int LN,RN;//L,R数目  
int g[maxn][maxn], linker[maxn];    //所连得边直接从做到右
bool used[maxn];  
int dfs(int L)//从左边开始找增广路径  
{  
    int R;  
    for(R = 1; R <= RN; R++)  
    {  
        if(g[L][R]!=0 && !used[R])  
        {  
            //找增广路，反向  
            used[R]=true;  
            if(linker[R] == -1 || dfs(linker[R]))  
            {  
                linker[R]=L;  
                return 1;  
            }  
        }  
    }  
    return 0;//这个不要忘了，经常忘记这句  
}  
int hungary()  
{  
    int res = 0 ;  
    int L;  
    memset(linker,-1,sizeof(linker));  
    for( L = 1; L <= LN; L++)  
    {  
        memset(used,0,sizeof(used));  
        if(dfs(L) != 0)  
            res++;  
    }  
    return res;  
}

二分图的完备匹配问题 （KM算法）

如果二分图的每条边都有一个权（可以是负数），要求一种完备匹配方案，使得所有匹配边的权和最大，记做最佳完美匹配。（特殊的，当所有边的权为1时，就是最大完备匹配问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
iint nx,ny;  //两边的点数
int g[maxn][maxn];   //建图
int linker[maxn],lx[maxn],ly[maxn];     //y中欧各个点的匹配状态,x y 中各个点的标号
int slack[maxn];        //松弛量数组
bool visx[maxn],visy[maxn];

bool dfs(int x)
{
    visx[x]=true;
    for(int y=0;y<ny;y++)
    {
        if(visy[y]) continue;
        int tmp=lx[x]+ly[y]-g[x][y];
        if(tmp==0)    //顶标符合要求，匈牙利算法寻找完备匹配
        {
            visy[y]=true;
            if(linker[y]==-1 || dfs(linker[y]))
            {
                linker[y]=x;
                return true;
            }

        }
        else if(slack[y]>tmp)
            slack[y] =tmp;        //更新松弛量
    }
    return false;
}

int KM()
{
    memset(linker,-1,sizeof(linker));     //初始化一开始匹配的点
    memset(ly,0,sizeof(ly));      //y的顶标先全部变成0
    //初始化顶标
    for(int i=0;i<nx;i++)
    {
        lx[i]= -INF;            //求最大值，首先初始化为最小值
        for(int j=0;j<ny;j++)
            if(g[i][j]>lx[i]) lx[i]=g[i][j];
    }
    for(int x=0;x<nx;x++)
    {
        for(int i=0;i<ny;i++)
            slack[i]=INF;
        //算法核心部分
        while(true)
        {
            memset(visx,false,sizeof(visx));
            memset(visy,false,sizeof(visy));
            if(dfs(x)) break;        //找到完备匹配，退出
            //没有找到完备匹配，在交错树中更改相关节点的顶标值
            int d= INF;
            //修改顶标，增加相等子图中的边
            for(int i=0;i<ny;i++)
                if(!visy[i] && d>slack[i])
                    d=slack[i];          //求出最小一个slack值
            for(int i=0;i<nx;i++)     //在交错树中的x的节点减少d
                if(visx[i])
                    lx[i]-=d;
            for(int i=0;i<ny;i++)        //在交错树中的y的节点增加d
            {
                if(visy[i]) ly[i]+=d;
                else
                    slack[i] -=d;          //x值减小，则相对的slack的值就会增大
            }
        }
    }
    int res=0;
    for(int i=0;i<ny;i++)
        if(linker[i]!=-1)
            res+=g[linker[i]][i];
    return res;
}

最大图问题

通俗来讲最大团问题就是在一个无向图中找出一个点数最多的完全图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
bool G[maxn][maxn];
int Max[maxn],Alt[maxn][maxn],ans,n;

bool dfs(int cur,int tot)     //cur 当前层次集合大小  tot 所在的层次
{
	if(cur==0)
	{
		if(tot>ans)
		{
			ans=tot;
			return 1;
		}
		return 0;
	}
	for(int i=0;i<cur;i++)
	{
		if(cur-i+tot<=ans) return 0;    //剪枝1
		int u=Alt[tot][i];    //选取当前考虑的点
		if(Max[u]+tot<=ans) return 0;
		int next=0;
		for(int j=i+1;j<cur;j++)
		{
			if(G[u][Alt[tot][j]])  Alt[tot+1][next++]=Alt[tot][j];
		}
		if(dfs(next,tot+1)) return 1;
	}
	return 0;
}

void  MaxClique()
{
	ans=0;
	memset(Max,0,sizeof(Max));
	for(int i=n-1;i>=0;i--)    //逆向构建Max
	{
		int cur=0;
		for(int j=i+1;j<n;j++) 
			if(G[i][j]) Alt[1][cur++]=j;
		dfs(cur,1);
		Max[i]=ans;
	}
}

最大流问题

给定指定的一个有向图,其中有两个特殊的点源S(Sources)和汇T(Sinks),每条边有指定的容量(Capacity),求满足条件的从S到T的最大流(MaxFlow).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int G[SIZE_V][SIZE_V];
int prev[SIZE_V];  //每个结点对应的前驱结点
bool visited[SIZE_V];
int V,E;

int Augment()  //使用bfs一次找出一条增广路
{
    int v,i;
    queue<int> q;
    memset(prev,0,sizeof(prev));
    memset(visited,0,sizeof(visited));
    prev[1]=0;
    visited[1]=1;
    q.push(1);
    bool bfindpath=0; //标识是否找到增广路
    while(!q.empty())
    {
        v=q.front();
        q.pop();
        for(i=1;i<=V;i++)
        {
            if(G[v][i]>0&&!visited[i]) //边上依然有容量可以走
            {
                prev[i]=v;
                visited[i]=1;
                if(i==V)  //找到一条增广路
                {
                    bfindpath=true;
                    q=queue<int> ();  //清空队列
                    break;
                }
                else
                    q.push(i);
            }
        }
    }
    if(!bfindpath)  //没有找到增广路
        return 0;
    //找出这条流的流量，即增广路上的最小边
    int minflow=INF;
    v=V;
    while(prev[v])
    {
        minflow=min(minflow,G[prev[v]][v]);    //注意是正向流量
        v=prev[v];
    }
    //改变流量，添加反向边
    v=V;
    while(prev[v])
    {
        G[prev[v]][v]-=minflow;
        G[v][prev[v]]+=minflow;
        v=prev[v];
    }
    return minflow;
}

int maxflow=0;
int aug;
while(aug=Augment())  //不断寻找增广路，直到找不到为止
    maxflow+=aug;