第三章 搜索与图论

DFS和BFS

DFS的一些tips

1. 有的时候需要恢复现场，在一个DFS后要恢复到DFS前的状态

BFS的一些tips

1. 基本结构是先加入一个到队头，然后只要队列不空(while)，取出队头
2. 根据队头元素关系，继续加入一些点到队列中

难题：八数码AcWing 845. 八数码 - AcWing

树和图的深度和广度优先遍历

树和图的存储

邻接矩阵(稠密图主要使用这个,$m$和$n^2$相当)：g[a][b]存储a->b

和邻接表(稀疏图主要使用这个,$m$和$n$相当)：模拟单链表

//对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N],e[N],ne[N],idx;
//添加一条边，a->b,无权值
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//初始化
idx=0;
memset(h,-1,sizeof h);

树和图的遍历

时间复杂度$O(n+m)$，n为点数，m为边数

DFS模板

int dfs(int u){
    st[u]=true;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j])dfs(j);
    }
}

BFS模板

queue<int> q;
st[1]=true;
while(q.size()){
    int t=q.front();
    q.pop();
    for(int i=h[t];i!=-1;i=ne[i]){
        int j=e[i];
        if(!st[j]){
            st[j]=true;
            q.push(j);
        }
    }
}

拓扑排序

==有向无环图一定存在拓扑排序==

1. 先把所有入度为0的点插入队列

2. 用宽度优先搜索，枚举queue的队头t所有出边(并不是真出，否则需要一个数组存储)，出边的入度减一，若变为0，则加入队列

3. 若将所有点都遍历过了，则存在拓扑排序，输入队列即可

最短路

最短路算法总概述

重点是，如何将问题抽象成最短路问题，而不是各个算法的证明

graph LR
root[最短路]-->单源最短路-->所有边权都是正数--稠密图-->朴素Dijkstra算法-.->o1(n^2)
所有边权都是正数--稀疏图-->堆优化版的Dijkstra算法-.->o2(mlogn)
单源最短路-->存在负权边--限定经过多少次边k-->Bellman-Ford-.->o3(nm)
存在负权边--不限定经过多少次边k-->SPFA-.->o4(一般m,最坏nm)
root-->多源汇最短路-->Floyd算法-.->05(n^3)

Dijkstra

思路过程：

1. 初始化，起点到起点距离为0，其他为正无穷
2. 在所有未确认到起点最短路的点中，寻找距离最小的点t
3. 将t加入确定最短路的集合中
4. 根据t更新其他点到起点的距离

朴素版Dijkstra，时间复杂度 $O(n^2+m)$ ,适合稠密图，即 $m$ 和 $n^2$ 相当，使用邻接矩阵

int g[N][N];//存储每条边的权值
int dist[N];//存储u号点到每个点的最短距离
bool st[N];//存储u到每个点的最短路是否已经确定
//求点u到n号点的最短路，如果不存在则返回-1
int dijkstra(int u){
    memset(dist,0x3f,sizeof dist);
    dist[u]=0;
    for(int i=1;i<=n;i++){
        int t =-1;//在还未确定最短路的点中，寻找距离最小的点
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[t]>dist[j])){
                t=j;
            }
        }
        //用t更新其他点的距离
        for(int j=1;j<=n;j++){
            dist[j]=min(dist[j],dist[t]+g[t][j]);
        }
        st[t]=true;
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}

堆加速版Dijkstra，时间复杂度 $O(m\log(n))$ ,即 $m$ 和 $n$ 相当，使用邻接表

typedef pair<int,int> PII;
int n;
int h[N],w[N],e[N],ne[N],idx;// 邻接表存储所有边
int dist[N]; //存储所有点到点1的距离
bool st[N]; //存储每个点的最短距离是否已经确定

//求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra(){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    q.push({0,1});//先距离，后点，是因为插入堆时先比较first，后比较second
    while(q.size()){
        auto t=q.top();
        q.pop();
        int ver =t.second,distence=t.first;
        if(st[ver])continue;
        st[ver]=true;
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(!st[j] && dist[j]>distence+w[i]){
                dist[j]=distence+w[i];
                q.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f)return -1;
    else return dist[n];
}
// 初始化
memset(h,-1,sizeof h);

bellman-ford

无需邻接表和邻接矩阵，直接使用一个边的结构体存储边即可。时间复杂度 $O(nm)$

思路过程：

1. 对于每个点，遍历所有边
2. 若有从别处来的点加上两点之间的边的距离小于本身到起点距离，则更新(dist[b]=min(dist[b],dist[a]+w))

==对每条边的迭代，迭代k次，表示经过不超过k条边的最短路==

模板：

int n,m;//n表示点数，m表示边数
int dist[N]，backup[N];//dist[x]存储x点到起点1的最短距离
struct Edge{
    int a,b,w;
}edges[M];
//求1到n的最短距离，如果无法从1走到n，则返回-1
int bellman_ford(){
    memset(dist,0x3f,sizeof dist);

    dist[1]=0;
    for(int i=1;i<=n;i++){
        memcpy(backup,dist,sizeof dist);
        for(int j=1;j<=m;j++){
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            dist[b]=min(dist[b],backup[a]+w);
        }
    }
    if(dist[n]>0x3f3f3f3f/2)return -1;
    else return dist[n];
}

spfa

利用队列优化bellman-ford,每次只更新修改了最短路的后继节点,迭代的时候用队列

时间复杂度平均 $O(m)$ ，最坏情况 $O(nm)$

模板：

int n;//点数
int h[N],e[N],ne[N],idx;//邻接表存储所有边
int dist[N];//存储每个点到1号点的最短距离
bool st[N];//存储每个点是否在队列中
//求1号点到n号点的最短路距离。如果不存在则返回-1
int spfa(){
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    st[1]=true;
    queue<int> q;
    q.push(1);
    while(q.size()){
        int t=q.front();
        q.pop();
        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                if(!st[j]){
                    st[j]=true;
                    q.push(j);
                }
            }
        }
    }
    return dist[n];
}
//初始化
memset(h,-1,size0f h);

Floyd

邻接矩阵存储所有边 D[N][N]

时间复杂度 $O(n^3)$

//初始化
const int INF=1e9;
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        if(i==j)d[i][j]=0;
        else d[i][j]=INF;
    }
}
//算法结束后，d[a][b]表示a到b的最短距离
void floyd(){
    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]);
            }
        }
    }
}

最小生成树

==对应的图都是无向图==

稠密图用朴素Prim，稀疏用Kruskal，堆优化prim一般不用

graph LR
最小生成树-->prim算法-->朴素版prim-.->o1(n^2)
prim算法-->堆优化版prim-.->o2(mlogn)
最小生成树-->kruskal算法-.->o3(mlogm)

Prim

算法思路：

1. 首先，初始化所有点到最小生成树集合距离为正无穷
2. 遍历所有点，找到集合外，距离最近的点t
3. 用t更新其他点到==集合==的距离，并把t加入集合中

和Dijkstra不同的点在于高亮中。

时间复杂度：$O(n^2+m)$

模板：

int n;//表示边数
int g[N][N];//邻接矩阵，存储所有边
int dist[N];//存储其他点到当前最小生成树集合的最短距离
int st[N];//存储一个点是否已经在生成树集合上了

//如果图不连通，则返回0x3f3f3f3f，否则返回最小生成树的树边权重之和
int prim(){
    memset(dist,0x3f,sizeof dist);
    int res=0;
    for(int i=0;i<n;i++){
        int t=-1;
        for(int j=1;j<=n;j++){
            if(!st[j] && (t==-1 || dist[j]<dist[t]))t=j;
        }
        if(i && dist[t]==0x3f3f3f3f)return 0x3f3f3f3f;//如果不是第一次并且最短边还是inf，则不存在最短路
        if(i)res +=dist[t];//如果不是第一个点，最小生成树距离加上当前点t
        st[t]=true;
        for(int j=1;j<=n;j++)dist[j]=min(dist[j],g[t][j]);
    }
    return res;
}

Kruskal

算法思路：

1. 将所有边按权重从小到大排序 $O(m\log m)$
2. 枚举每条边a，b，权重c
3. 如果a，b不连通，将这条边加入集合

const int INF=0X3f3f3f3f;
int n,m; //n是点数，n是边数
int p[N];

struct Edge{
    int a,b,w;
    bool operator< (const Edge &W)const{
        return w<W.w;
    }
}edges[M];

//并查集核心操作
int find(int x){
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
//kruskal算法，如果存在最小生成树，返回边权之和；否则返回INF
int kruskal(){
    sort(edges,edges+m);//根据边权从小到大排序
    for(int i=1;i<=n;i++)p[i]=i;//初始化并查集
    int res=0,cnt=0;
    for(int i=1;i<=m;i++){
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        int pa=find(a),pb=find(b);
        if(pa!=pb){
            p[pa]=pb;
            res+=w;
            cnt++;
        }
    }
    if(cnt<n-1)return INF;
    else return res;
}

二分图

二分图当且仅当图中不含奇数环(二部图)

染色法判定二分图

就是用深度优先遍历所有的点

int n;      // n表示点数
int h[N], e[M], ne[M], idx;     // 邻接表存储图
int color[N];       // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色

// 参数：u表示当前节点，c表示当前点的颜色
bool dfs(int u, int c)
{
    color[u] = c;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (color[j] == -1)
        {
            if (!dfs(j, !c)) return false;//表示矛盾
        }
        else if (color[j] == c) return false;//表示矛盾
    }

    return true;//表示没矛盾
}

bool check()
{
    memset(color, -1, sizeof color);
    memset(h,-1,sizeof h);
    bool flag = true;
    for (int i = 1; i <= n; i ++ )
        if (color[i] == -1)
            if (!dfs(i, 0))
            {
                flag = false;
                break;
            }
    return flag;
}

匈牙利算法

二分图最大匹配问题，一般时间复杂度 $O(n)$ ，最差为 $O(nm)$

int n1,n2; //n1表示男生个数，n2表示女生个数
int h[N],e[M],ne[M],idx; //邻接表存储所有边，匈牙利算法只会用到男生到女生的边(心上人)，这里只用存一个方向
int match[N];//存储女生当前暂时和哪个男生组成了cp，若还没，则为0
bool st[N];//表示女生是否已经被遍历到

//返回当前男生是否能找到一个女生组cp，若能则返回true；反之false
bool find(int x){
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];//枚举他心动的女生
        if(!st[j]){
            st[j]=true;
            if(match[j]==0 || find(match[j])){//如果心动的女生还没cp或者她的cp还能找到别的女生
                match[j]=x;//心动女生就跟当前男生组新cp
                return true;
            }
        }
    }
    return false;
}
//求最大匹配，依次枚举每个男生，看他能否找到cp
int res=0;
for(int i=1;i<=n1;i++){
    memset(st,false,sizeof st);
    if(find(i))res++;
}