图算法合集

邻接表存储图

数组s存储的是所有对应编号节点连的边(抛弃了以前的邻接表头部分，更简洁)

typedef struct node {
    int data;
    long long w;
    struct node *link;
} Node, *Nodeprt;
Nodeprt s[100005];

节点编号和权重

Nodeprt buildEdge(int data,long long w){
    Nodeprt p = (Nodeprt)malloc(sizeof(Node));
    p->data=data;
    p->w=w;
    p->link = NULL;
    return p;
}

插入每条边，直接从头部插入，然后更新头部，提高效率，避免每次寻找链表尾部

插入的时候，如果是无向图，需要用两次插入函数

void insertEdge(int u,int v,long long w){
    Nodeprt p = buildEdge(v,w);
    if(s[u]==NULL)s[u]=p;
    else{
        p->link=s[u];
        s[u]=p;
    }
}

邻接表存图，如果多组数据，需要删除当前有的边

void deleteEdge(int n){//删除所有顶点连接的边
    for(int i=1;i<=n;i++){
        for(Nodeprt p = s[i];p!=NULL;){
            Nodeprt q = p;
            p=p->link;
            free(q);
        }
        s[i]=NULL;
    }
}

堆

在后面的学习中，基本所有算法对时间都有一个比较高的要求，因此基本能使用堆的地方都尽可能使用堆优化，每次自己都手写一遍

堆节点及其存储(这里以对结构体的节点编号和距离为例子)

typedef struct edge {
    int data;
    long long w;
}Edge,*Edgeprt;
Edge Heap[500005];
int size=0;

堆的插入，每次插入到末尾，然后自顶向上更新，对堆进行向下过滤

小顶堆

void insertHeap(int data,long long w){
    Edge p = {data,w};
    size++;
    int i=size;
    while(i>=2){
        //看当前位置值是否比父亲小，如果小，就把父亲过滤下来
        if(p.w<Heap[i/2].w)Heap[i]=Heap[i/2];
        else break;
        i/=2;//往上走一层
    }
    Heap[i]=p;
}

大顶堆

void insertHeap(int data,long long w){
    Edge p = {data,w};
    size++;
    int i=size;
    while(i>=2){
        //看当前位置是否比父亲大，如果大，就把父亲过滤下来
        if(p.w>Heap[i/2].w)Heap[i]=Heap[i/2];
        else break;
        i/=2;//往上走一层
    }
    Heap[i]=p;
}

堆的删除，返回堆顶元素，删除堆顶之后，把末尾元素放到堆顶，然后自顶向下更新，向上过滤

小顶堆

Edge deleteHeap(){
    Edge res = Heap[1];//先保存返回值
    Heap[1]=Heap[size--];//把末尾元素放到堆顶
    int i=2;
    while(i<=size){
        //寻找这一层左右两个点中较小的值
        if(i+1<=size&&Heap[i].w>Heap[i+1].w)i++;
        //看当前位置是否比父亲小，如果小，就交换位置
        if(Heap[i].w<Heap[i/2].w){
            Edge tmp = Heap[i];
            Heap[i]=Heap[i/2];
            Heap[i/2]=tmp;
        }else break;
        i*=2;//往下走一层
    }
    return res;
}

大顶堆

Edge deleteHeap(){
    Edge res = Heap[1];//先保存返回值
    Heap[1]=Heap[size--];//把末尾元素放到堆顶
    int i=2;
    while(i<=size){
        //寻找这一层左右两个点中较大的值
        if(i+1<=size&&Heap[i].w<Heap[i+1].w)i++;
        //看当前位置是否比父亲大，如果大，就交换位置
        if(Heap[i].w>Heap[i/2].w){
            Edge tmp = Heap[i];
            Heap[i]=Heap[i/2];
            Heap[i/2]=tmp;
        }else break;
        i*=2;//往下走一层
    }
    return res;
}

最短路

Dijkstra

可以有向图，无向图，但是不能有负权值

单源最短路径，给定点src，到其它所有编号点的最短距离

final数组表示当前哪些点的最短距离已经求过了，计算过了就设置为1

正常复杂度为$O(V^2+E)$，堆优化后为$O((V+E)logE)$

long long dis[100005];//src点到所有编号点的最短距离
void dijkstra(int src,int n){
    int final[100005];
    for(int i=1;i<=n;i++){
        final[i]=0;
        dis[i]=MAX;//最开始到所有点的距离为无穷大
    }
    final[src]=1;
    dis[src]=0;//加入源点
    //把源点所有连接的点加入到堆里面，提高返回最小距离的效率
    for(Nodeprt p = s[src];p!=NULL;p=p->link){
        dis[p->data]=p->w;
        insertHeap(p->data,p->w);
    }
    while(size!=0){
        //每次找到最短距离，并且得是没有加入到final的点
        Edge p = deleteHeap();
        int k=p.data;
        long long w = p.w;
        if(final[k]==0){
            //找到一个最短路径的点，就更新这个点所有相连的点，同样是加入堆
            final[k]=1;
            for(Nodeprt q=s[k];q!=NULL;q=q->link){
                //只要是相连的，并且没有加入到final的，都要考虑
                if(final[q->data]==0){
                    //加入堆之前先更新一下距离
                    if(dis[q->data]>q->w+w)dis[q->data]=q->w+w;
                    insertHeap(q->data,dis[q->data]);
                }
            }
        }
    }
}

Floyed

无负权回路，正权都可以，求解任意两点之间的最短路径，有向图或者负权，传递闭包，复杂度$O(n^3)$

适用于稠密图，快于V次Dijkstra

int map[1005][1005];
void init(int n){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j)map[i][j]=0;
            else map[i][j]=MAX;
        }
    }
}
//输入所有边，对于i到j有边，就设置为对应权值
void Floyed(int n){
    for(int k=1;k<=n;k++){//选取中介点，从第一个点到最后一个点
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(map[i][j]>map[i][k]+map[k][j]){
                    map[i][j]=map[i][k]+map[k][j];
                    path[i][j]=k;
                }
            }
        }
    }
}

Spfa

可以用来判断负环

首先入队列源点，然后出队，对于出队的点，更新所有与它有关的距离，如果距离被更新，并且被更新的点不在队列中，那就入队

这样每次从出队一个元素，更新所有距离，如果距离被更新，并且被更新的点不在队列，就入队

直到最终队列里面为空为结束

负环的判断：负环说明没有最短路径，如果一个点入队n次(n为节点总数量)那就说明存在负环

时间复杂度$O(VE)$

Edgeprt E[100005];
long long dis[100005];
int queue[100005];
int front = 0, rear = 0;
int Spfa(int src, int n) {
    int final[100005];
    int cnt[5005];//记录每个节点入队的次数
    for (int i = 1; i <= n; i++) {
        final[i] = 0;
        dis[i] = MAX;
    }
    queue[rear++] = src;
    cnt[src]++;
    final[src] = 1;
    dis[src] = 0;
    while (front != rear) {
        int q = queue[front++];
        final[q] = 0;
        for (Edgeprt p = E[q]; p != NULL; p = p->link) {
            if (p->w + E[q]->w < dis[p->data]) {
                dis[p->data] = p->w + E[q]->w;
                if (final[p->data] == 0) {
                    queue[rear++] = p->data;
                    cnt[p->data]++;
                    if (cnt[p->data] > n)return 1;//入队次数过多，负环存在
                }
            }
        }
    }
    return 0;//到这说明正常运行，无负环
}

最小生成树

Prim

final数组记录加入到最小生成树的点

从一个点，每次找最近的点，最终把所有点加入到最小生成树

正常复杂度为$O(V^2+E)$，这里使用了堆优化复杂度为$O((E+V)logE)$

long long prim(int n, int src) {
    long long result = 0;//最小生成树总权重，唯一，但是树的形状可能不唯一
    for (int i = 1; i <= n; i++) {
        final[i] = 0;
    }
    final[src] = 1;
    //把源点相连的边都加入堆，方便后面返回最近的点
    for (Nodeprt p = s[src]; p != NULL; p = p->link) {
        insertHeap(p->data, p->weight);
    }
    while (size != 0) {
        //每次返回最短的距离的点
        Edge p = deleteHeap();
        int k = p.data;
        long long w = p.weight;
        if (final[k] == 0) {
            //把这个最短距离加入到总权重中，将这个点加入最小生成树集合
            result += w;
            final[k] = 1;
            //对于这个点，把它所有相连的点加入到堆
            for (Nodeprt q = s[k]; q != NULL; q = q->link) {
                if (final[q->data] == 0) {
                    insertHeap(q->data, q->weight);
                }
            }
        }
    }
    return result;
}

Kruskal

Kruskal算法不需要真正构建图，只需要把所有边都存起来就行，因此直接用结构体存储每条边

typedef struct edge {
    int u;
    int v;
    long long w;
} Edge, *Edgeprt;
Edge s[500005];

按照边的权重从小到大排序，然后依次考虑每条边，看能否加入最小生成树

加入的判断过程，就是看加入这条边是否会形成环，这里采用并查集判断

int S[100005];//记录每个树的高度
int root[100005];//记录每个点的根
int Find(int x){
    if(root[x]<0)return x;
    else return root[x]=Find(root[x]);//路径压缩查找根
}
void Union(int x,int y){
    int rootX = Find(x);
    int rootY = Find(y);
    if(rootX!=rootY){
        if(S[x]>S[y]){
        	root[rootY]=rootX;
    	}
        else if(S[x]<S[y]){
            root[rootX]=rootY;
        }
        else{
            root[rootY]=rootX;
            S[x]++;
        }
    }
    
}
long long Kruskal(int m){//m为边的个数
    qsort(s,m,sizeof(s[0]),cmp);//cmp按照权重从小到大排序
    int u,v;
    long long ans=0;
    for(int i=0;i<m;i++){
        u=s[i].u;v=s[i].v;
        if(Find(u)!=Find(v)){//加入这条边不会形成环
            ans+=s[i].w;
            Union(u,v);
        }
    }
}

拓扑排序Topo

有向图，先插入边的时候记录一下每个点的入度

首先把所有入度为0的点加入，然后每次返回一个点，再把这个点所有连接的点的入度减一

直到最后所有点都在拓扑序列里，这里用了堆优化，可能同时有多个点入度为0，序号大的先输出

int num[100005];//在插入边的时候记录一下每个点的入度(有向图)
void Topo(int n) {
    //先把所有入度为0的点加入到堆，因为这里要求字典序大的先输出，可能同时有多个点入度为0
	for (int i = 1; i <= n; i++) {
		if (num[i] == 0) {
			insertHeap(i);
		}
	}
	while (size != 0) {
		int p = deleteHeap();
		if (p == -1)break;
		printf("%d ", p);
		for (Nodeprt q = s[p]; q != NULL; q = q->link) {
			num[q->data]--;
			if (num[q->data] == 0) {
				insertHeap(q->data);
			}
		}
	}
}

二分图匹配

Hungary匈牙利算法(无权二分图最大匹配)

参考教程

无权二分图最大匹配

最大匹配：让两个集合的点互相配对，同一个点最多只能和一个点配对，最多的配对数量

最小覆盖：求最少数量的点，删除包含这些点的边，能够删除二分图所有边，这些点的数量和最多配对数量一样

匈牙利算法是一个用于解决该类问题的标准算法之一，核心想法是"让路"：假设你当前想配对Bi与Gk，但是Gk已经有了对象Bj，此时就和Bj交涉能否让Bj尝试换一个对象，如果Bi能够换一个对象，就可以配对Bi与Gk；否则配对失败。

int map[405][405];//记录第一个集合的点到第二个集合的点是否有边
int mate[405];//第二个集合的点对应的配对第一个集合的点的编号
int visit[405];//第二个集合的某个点是否访问过
int match(int x,int n){
    for(int i=1;i<=n;i++){
        if(map[x][i]&&!visit[i]){
            visit[i]=1;
            if(!mate[i]||match(mate[i],n)){
                mate[i]=x;return 1;
            }
        }
    }
    return 0;
}
void Hungary(){
    int res=0;
    for(int i=1;i<=n;i++){//依次对第一个集合的所有点去匹配
        for(int j=1;j<=n;j++)visit[j]=0;
        if(match(i,n))res++;
    }
    printf("%d",res);
}

KM算法(带权二分图最大匹配)

KM 算法是用于求带权二分图的最优匹配的算法，其时间复杂度为 $O(n^4)$

1.首先选择顶点数较少的为 X 部（左点集），初始时对 X 部的每一个顶点设置顶标，顶标的值为该点关联的最大边的权值，Y 部（右点集）的顶点顶标为 0。

2.对于 X 部中的每个顶点，在相等子图中利用匈牙利算法找一条增广路径，如果没有找到，则修改顶标，扩大相等子图(边权等于两个顶点顶标的和的边组成的图)，继续找增广路径。

3.当 X 部的每个点都找到增广路径时，此时意味着每个点都在匹配中，即找到了该二分图的完全匹配。该完全匹配即为二分图的最优匹配。

ps: map[i][j]设置为对应的权值，如果不存在边就设置为-MAX

最小权就先把所有取负值，最后结果加上负号就行

这个稍微好理解一点，把顶标改成期望值

#define MAX 1e15
#define max(a, b) a>b?a:b
#define min(a, b) a>b?b:a
typedef struct point {
    int x;
    int y;
} Point, *Pointprt;
Point A[520], B[520];
long long map[520][520];//记录每条边的权
long long Lx[520], Ly[520];//左右顶点的顶标
int visX[520], visY[520];
int match[520];//记录右侧顶点匹配的左侧顶点标号
long long slack[520];//边权和顶标的最小差值
int DFS(int x, int m) {
    visX[x] = 1;
    for (int i = 1; i <= m; i++) {//遍历右侧顶点
        if (visY[i] == 0) {//右侧这个点没访问过,并且存在路径
            if (Lx[x] + Ly[i] - map[x][i] == 0) {//不在交替路中
                visY[i] = 1;//加入交替路
                if (match[i] == 0 || DFS(match[i], m) == 1) {//如果这个点没匹配，或者能为匹配过的点更换目标
                    match[i] = x;
                    return 1;
                }
            } else slack[i] = min(slack[i], Lx[x] + Ly[i] - map[x][i]);
            //slack[i]存储的是右侧的点需要变成相等子图顶标值最小增加多少
        }
    }
    return 0;//无法匹配
}

long long KM(int n, int m) {//m是右侧顶点数量，n是左侧顶点数量
    for (int i = 1; i <= n; i++)Lx[i] = -MAX;//x顶标要为最大权重
    for (int i = 1; i <= m; i++)Ly[i] = 0;//y顶标为0
    for (int i = 1; i <= m; i++)match[i] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            Lx[i] = max(Lx[i], map[i][j]);
        }
    }

    for (int i = 1; i <= n; i++) {

        while (1) {
            for (int j = 1; j <= m; j++)slack[j] = MAX;
            for (int j = 1; j <= n; j++) visX[j] = 0;
            for (int j = 1; j <= m; j++)visY[j] = 0;
            if (DFS(i, n) == 1)break;
            long long d = MAX;
            for (int j = 1; j <= m; j++) {
                if (!visY[j])d = min(d, slack[j]);
            }
            for (int j = 1; j <= n; j++) {//左侧顶标减去
                if (visX[j])Lx[j] -= d;
            }
            for (int j = 1; j<= m; j++) {//右侧顶标加上
                if (visY[j])Ly[j] += d;
                else slack[j] -= d;
                //修改顶标后，把所有不在交错树中的右侧顶点的slack值减去Min
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        if (match[i] != 0) {//存在边
            ans += map[match[i]][i];
        }
    }
    return ans;
}

优化$O(n^3)$，看不懂copy的模板思密达

#define MAX 1e15
#define pi 4000000000
#define max(a, b) a>b?a:b
#define min(a, b) a>b?b:a
typedef struct point {
    long long x;
    long long y;
} Point, *Pointprt;
Point A[520], B[520];
long long map[520][520];//记录每条边的权
long long Lx[520], Ly[520];//左右顶点的顶标
int visX[520], visY[520];
int match[520];//记录右侧顶点匹配的左侧顶点标号
long long slack[520];//边权和顶标的最小差值
int pre[520];

int BFS(int p, int m) {
    int x = 0, y = 0, yy = 0;
    for (int i = 0; i <= m; i++) {
        pre[i] = 0;
        slack[i] = MAX;
    }
    match[0] = p;
    do {
        long long d = MAX;
        x = match[y];
        visY[y] = 1;
        for (int i = 1; i <= m; i++) {
            if (visY[i])continue;
            if (slack[i] > Lx[x] + Ly[i] - map[x][i]) {
                slack[i] = Lx[x] + Ly[i] - map[x][i];
                pre[i] = y;
            }
            if (slack[i] < d) {
                d = slack[i];
                yy = i;
            }
        }
        for (int i = 0; i <= m; i++) {
            if (visY[i]) {
                Lx[match[i]] -= d;
                Ly[i] += d;
            } else slack[i] -= d;
        }
        y = yy;

    } while (match[y]);
    while (y) {
        match[y] = match[pre[y]];
        y = pre[y];
    }
}

long long KM(int n, int m) {//m是右侧顶点数量，n是左侧顶点数量
    for (int i = 1; i <= n; i++)Lx[i] = -MAX;//x顶标要为最大权重
    for (int i = 1; i <= m; i++)Ly[i] = 0;//y顶标为0
    for (int i = 1; i <= m; i++)match[i] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            visY[j] = 0;
        }
        BFS(i, m);
    }

    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        if (match[i] != 0) {//存在边
            ans += map[match[i]][i];
        }
    }
    return ans;
}

最大流问题

给定n个点，m条边，有向图，求s到t的最大流量，允许重边和自环，自环直接忽略，重边进行合并

使用Dinic算法，每次通过BFS寻找是否存在增广路径，然后通过DFS进行增广

使用邻接表存储，每次插入一条边时，都需要插入一条其反向的，流量为0的边

cur数组记录之前BFS到的位置，避免每次确认是否还有增广路径的时候的重复寻找，提升效率

int BFS(int s,int t){
    for(int i=1;i<=1000;i++){
        depth[i]=0;
    }
    front = rear = 0;
    queue[rear++]=s;
    depth[s]=1;
    cur[s] = E[s];
    while(front!=rear){
        s = queue[front++];
        for(Edgeprt p = cur[s];p!=NULL;p=p->link){
            if(p->flow>0&&depth[p->data]==0){//这条边还可以有流量，并且没有访问过
                depth[p->data]=depth[s]+1;
                cur[p->data] = E[p->data];
                if(p->data==t)return 1;
                queue[rear++]=p->data;
            }
        }
    }
    return 0;
}
long long DFS(int s,long long flow,int t){
    if(s==t||flow<=0)return flow;//找到t就返回此时增广路径的流量
    long long rest = flow;
    for(Edgeprt p = cur[s];p!=NULL;p=p->link){
        if(p->flow > 0 && depth[p->data] ==depth[s]+1){//由深度和流量不为0确认是增广路径
            long long tmp = DFS(p->data,min(rest,p->flow),t);//对下一个节点寻找增广路径，流量取最小
            if(tmp<=0)depth[p->data]=0;//tmp小于等于0为阻塞路径，也就是对之前的增广进行反悔
            rest-=tmp;
            p->flow-=tmp;
            p->rev->flow+=tmp;
            if(rest<=0)break;
        }
    }
    return flow-rest;//剩余流量减去增广之后的剩余流量，就是此次增广的流量
}
long long Dinic(int s,int t){
    long long ans = 0;
    while(BFS(s,t)){
        ans+=DFS(s,MAX,t);
    }
    return ans;
}