搜索与图论

DFS

深度优先搜索：尽可能的往深度的方向搜索，当搜索到头的时候就回溯，搜索到的路径不具有最短路的性质；
“不撞南墙不回头”
使用stack来实现
空间： $O(n)$

DFS算法没有固定模板，重要的是思路

如何用DFS解决全排列问题？

#include <iostream>
using namespace std;

const int N = 10;

int n;
int path[N]; // 对应状态
bool st[N]; 

void dfs(int u)
{
    if(u == n)
    {
        for(int i=0;i<n;i++) print("%d",path[i]);
        puts("");
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
    { 
            path[u] = i;
            st[i] = true; // 状态修改
            dfs(u+1);
            st[i] = false; // 恢复现场
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    return 0'
}

DFS解决n皇后问题

第一种搜索顺序：枚举每一行

需要注意减枝的问题；

#include <iostream>
using namespace std;

const int N = 20;

int n;
char g[N][N]; // 对应状态
bool col[N],dg[N],udg[N]; 

void dfs(int u)
{
    if(u == n)
    {
        for(int i=0;i<n;i++) puts(g[i]);
        puts("");
        return;
    }
    for(int i=0;i<n;i++)
    {
        if(!col[i] and !dg[u+i] and !udg[n-u+i])
        {
            g[u][i] = 'Q';
            col[i] = dg[u+i] = udg[n-u+i] = true; // 状态修改
            dfs(u+1);
            col[i] = dg[u+i] = udg[n-u+i] = false; // 恢复现场
            g[u][i] = '.';
        }
    }
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;i<n;j++)
            g[i][j] = '.'
    dfs(0);
    return 0;
}

第二种搜索顺序：更原始的枚举方法，一个格子一个格子的枚举

#include <iostream>
using namespace std;

const int N = 20;

int n;
char g[N][N]; // 对应状态
bool col[N],dg[N],udg[N]; 

void dfs(int x,int j,int s)
{
    if(y == n) y = 0,x++;
    if(x == n)
    {
        if(s == n)
        {
            for(int i=0;i<n;i++) puts(g[i]);
            puts("");
        }
        return;
    }

    // 不放皇后
    dfs(x,y+1,s);

    // 放皇后
    if(!row[x] and !col[y] and !dg[x+y] and !udg[x - y + n])
    {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        dfs(x,y+1,s+1);
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
        g[x][y] = '.';
    }
}

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;i<n;j++)
            g[i][j] = '.'
    dfs(0);
    return 0;
}

BFS

宽度优先遍历：会把所有的情况都囊括，一层层向外扩展，可以用来搜索最短路；
“眼观六路耳听八方”
使用queue来实现
空间： $O(2^n)$

注意：BFS不能求解带权重的最短路问题

BFS框架代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 110;
typedef pair<int,int> PII;
int n,m;
int g[N][N]; // 用于记录地图
int d[N][N]; // 用于记录距离
PII q[N*N]; // 模拟队列

int bfs()
{
    int hh=0, tt=0;
    q[0] = {0,0};
    memset(d,-1,sizeof d);
    d[0][0] = 0;
    int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
    while(hh <= tt)
    {
        auto t = q[hh++];
        for(int i =0;i<4;i++)
        {
            int x= t.first + dx[i],y = t.second + dy[i];
            if(x >=0 and x < n and y >= 0 and y < m and g[x][y] == 0 and d[x][y] == -1)
            {
                d[x][y] = d[t.first][t.second] +1;
                q[++tt] = {x,y};
            }
        }
        
    }
    return d[n-1][m-1];
}

int main()
{
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> g[i][j];
    cout << bfs() << endl;
}

树的重心

树是一种特殊的图，无环连通图
图分为两种，有向图与无向图
有向图：
邻接矩阵（比较费空间）
邻接表（就是单链表，和拉链法的哈希表的存储一样一样的）

图的深度搜索

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010, M = N *2;

int n,m;
int h[N],e[M],ne[M],idx;
bool st[N];
int ans = N;

// 添加节点
void add(int a,int b)
{
    e[idx]=b; ne[idx] = h[a];h[a] = idx++;

}

// 以u为根的子数的大小
int dfs(int u)
{
    st[u] = true; // 标记一下，已经被搜索过了
    int sum = 1, res = 0;
    for(int i = h[u]; i != -1;i = ne[i])
    {
        int j = e[i];
        if(!st[j]) 
        {
            int s = dfs(j); 
            res = max(res,s);
            sum += s;
        }
    }
    res= max(res,n-sum);
    ans = min(ans,res);
    return sum;

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b), add(b,a); // 无向图
    }
    dfs(1);
    cout << ans;
}

图的宽度搜索

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
int h[N],e[N], ne[N], idx;
int d[N], q[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int bfs(int t)
{
    int hh = 0, tt = 0;
    q[0] = 1; // 初始化队列
    memset(d, -1, sizeof(d));
    d[1] = 0; // 初始化距离矩阵
    while(hh <= tt)
    {
        int t = q[hh++]; // 取队头元素
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[t] + 1;
                q[++t] = j;
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1 ,sizeof h);

    for(int i = 0;i < m;i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    cout << bfs() << endl;
}

图的拓扑序列

有向无环图被称为拓扑图
拓扑图里重要的概念：
入度：一个点有多少条边指向自己，入度为0说明没有任何点在我前面
出度：一个点有多少条边出去

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;

int n,m;
int h[N],e[N],ne[N],idx;
int q[N],d[N];

void add(int a,int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort()
{
    int hh = 0, tt = -1;
    // 将所有的起点加入到队列当中
    for(int i = 1;i<=n;i++)
        if(!d[i])
            q[++tt] = i;
    while(hh < = tt)
    {
        int t = q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j = e[i];
            d[j]--; // 删除这个节点屁股上连的节点
            if(d[j] == 0) q[++tt] = j; 
        }
    }
    return tt == n - 1;
}

int main()
{

    cin >> n >> m;
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        d[b]++;
    }``
    if(topsort()) // 拓扑顺序就存在队列里面
    {
        for(int i = 0; i< n;i++) cout << q[i] << ' ';
        puts("");
    }else{
        puts("-1");
    }
}

最短路问题

常见的最短路问题可以分为两大类：
多源汇最短路：Floyd算法 O(n^3)
单源最短路：
(1) 所有边权都是正数：a. 朴素Dijkstra算法 b. 堆优化版的Dijkstra算法
(2) 存在负权边：a. Bellman-Ford O(nm) b. SPFA O(m)

朴素版Dijkstra算法

s : 已经确定最短路径的点
初始化距离
循环n次，找到不在s中的点t，用t更新其他点的距离（每次迭代都可以确定一个点的距离）时间复杂度：O(n^2)

使用邻接矩阵去存储图

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int dijkstra()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0; // 初始化第一个节点
    for(int i = 0; i<n;i++)
    {
        int t = -1;
        for(int j=1;j<=n;j++)
            if(!st[j] and (t == -1 || dist[t] > dist[j])) t = j;
        st[t] = true;
        // 已经找到最短路径
        if(t == n) break;
        // 更新最短距离
        for(int j=1;j<=n;j++)
            dist[j] = min(dist[j],dist[t]+g[t][j]);
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

int main()
{
    cin >> n >> m;
    memeset(g,0x3f,sizeof g)
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = min(g[a][b],c);
    }
    int t = dijkstra();
    cout << t;
    return 0;
}

堆优化的Dijkstra算法

使用堆(优先队列)来存储图
时间复杂度：O(mlogn)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 150010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
int dist[N],st[N];

int dijkstra()
{
    memset(dist, 0x3f,sizeof dist);
    dist[1] = 0;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    heap.push({0,1});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i = h[ver];i!=-1;i=ne[i])
        {
            int j = e[i];
            if(dist[j] > distance + w[i])
            {
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

void add(int a,int b,int c)
{
    e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}


int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    int t = dijkstra();
    cout << t;
    return 0;
}

Bellman-Ford算法

两重循环，第一层循环就循环n次，第二次循环更新最短距离
处理有负权边的搜索，如果有负权回路的话，最短路不一定存在
适用场景：==最多只能有k条边的时候==
时间复杂度：O(n,m)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510,M = 10010;

int n,m,k;
int dist[N],backup[N];

struct Edge
{
    int a,b,w;
}edges[M];

int bellman_ford()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;

    for(int i=0;i<k;i++)
    {
        // 备份, 因为可能出现串联的情况
        memcpy(backup, dist, sizeof dist);
        for(int j =0;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;
    return dist[n];
}

int main()
{
    cin >> n >> m >> k;
    for(int i =0;i<m;i++)
    {
        int a,b,w;
        cin >> a >> b >>  w;
        edges[i] = {a,b,w};
    }

    int t = bellman_ford();
    if(t == -1) cout << "impossible";
    else cout << d[n];
}

spfa算法

只要图里面没有负环就可以用spfa
spfa算法是对bellman-ford算法，bellman-ford算法每次会对每一个边进行优化，spfa就是对这点进行优化，使用宽搜进行优化
时间复杂度：一般O(m), 最坏O(nm)
但是有些出题人会卡spfa，让spfa算法的时间复杂度变为O(nm)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

int dist[N],bool st[N];

int add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++
}

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = true; // 判断点是否在退了当中，防止存储重复的点

    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])
                {
                    q.push(j);
                    st[j] = true;
                }
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];
}

int main()
{
    cin >> n >> m;
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    int t = spfa();
    cout << t;
}

spfa还可以判断环，使用一个cnt数据来进行记录即可

Fold算法

多源最短路算法
用邻接矩阵存储所有的边
时间复杂度：O(n^3)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N  =210,INF=1e9;

int n,m,Q;
int d[N][N];

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]);
}

int main()
{
    cin >> n >> m >> Q;
    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;
    while(m--)
    {
        int a,b,c;
        cin >> a > b > c;
        d[a][b] = min(d[a][b],c);
    }
    floyd();
    while(Q--)
    {
        int a,b;
        cin >> a >> b;
        if(d[a][b] > INF/2) cout << "impossible" << endl;
        else cout << d[a][b] << endl;
    }
}

最小生成树

tip

最小生成树对应的问题一般都是无向图；

两个经典的算法：

（1）prim算法：

1.朴素版Prim算法  O(n^2) （对应稠密图）
2.堆优化版的Prim算法 O(nm) （对应稀疏图）

（2）Kruskal算法 O(mlogm)

tip

如何选择哪一种算法：

稠密图选朴素版prim算法，稀疏图选择Kruskal算法

朴素版prim算法

tip

思路：

(1) 初始化距离为正无穷

(2) 循环，每次循环找到集合外距离最近的点t，用t更新其他点到集合的距离

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N = 510,INF=0x3f3f3f3f;

int n,m;
int g[N][N];
int dist[N];
bool st[N];

int prim()
{
    // 初始化距离为正无穷
    memset(dist,0x3f,sizeof dist);
    int res=0;
    // 循环n次
    for(int i=0;i<n;i++)
    {
        int t = -1;
        // 寻找集合外最近的点t
        for(int j=1;j<=n;j++)
            if(!st[j] and (t==-1 or dist[t] > dist[j])) 
                t=j;
        if(i and dist[t] == INF) return INF;
        if(i) res += dist[t]; // 注意这里的顺序不能颠倒
        // 使用t去更新其他点到集合的最短距离
        for(int j=1;j<=n;j++) dist[j] = min(dist[j],g[t][j]);
        st[t] = true;
    } 
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g,0x3f,sizeof g);
    while(m--)
    {
        int a,b,c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b],c);
    }
    int t = prim();
    if(t==INF) puts("impossible");
    else cout << t;
}

Kruskal算法

tip

用于解决稠密图的问题

思路：

(1) 先将所有边按照权重从小到大排序 O(mlogn)

(2) 枚举每条边ab，权重c，如果a和b不连通就将这条边加入到集合当中 (使用并查集来完成)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n,m;
int p[N];

// 使用结构体存储所有的边
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        int a,b,w;
        cin >> a >> b >> w;
        edges[i] = {a,b,w};
    }
    // 根据权重对所有边从小到大排序
    sort(edges,edges+m);
    for(int i=1;i<=n;i++) p[i] = i;
    int res = 0,cnt = 0;
    // 循环每一条边，如果两个边的节点不在一个集合中就将边加入到集合当中
    for(int i=0;i<m;i++)
    {
        int a = edges[i].a,b = edges[i].b,w = edges[i].w;
        a = find(a);
        b = find(b);
        if(a != b)
        {
            p[a] = b;
            res += w; // 记录最短权重
            cnt++; // 记录连通的边的个数
        }
    }
    if(cnt < n-1) puts("impossible");
    else cout << res;
}

二分图

tip

对于二分图：顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

tip

判断二分图的两种方法

(1) 染色法 O(n+m)

(2) 匈牙利算法 O(nm)，实际运行时间一般远小于O(nm)

染色法

tip

代码思路：

染色可以使用1和2区分不同颜色，用0表示未染色
遍历所有点，每次将未染色的点进行dfs, 默认染成1或者2
由于某个点染色成功不代表整个图就是二分图, 因此只有某个点染色失败才能立刻return
染色失败相当于存在相邻的2个点染了相同的颜色

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010, M = 200010;

int h[N],e[M],ne[M],idx;
int color[N]; // 格子一共有两种颜色1和2
int n,m;

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

// 返回时候能够把u染成颜色c
bool dfs(int u,int c)
{
    // 修改当前颜色
    color[u] = c;
    // 遍历和u相连通的所有格子
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j = e[i]; // 获取当前格子的编号
        if(!color[j])
        {
            // 没有染色的点，递归进行染色
            if(!dfs(j,3-c)) return false; 
        }
        // 如果染过色且和c颜色相同
        else if(color[j] == c) return false;
    }
    return true;
}

int main()
{
    cin >> n >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    bool flag = true;
    // 循环n次
    for(int i=1;i<=n;i++)
    {
        // 格子没有进行染色
        if(!color[i])
        {
            // 深搜判断颜色是否会发生冲突
            if(!dfs(i,1))
            {
                flag = false;
                break;
            }
        }
    }
    if(flag) puts("Yes");
    else puts("No");
    
}

匈牙利算法

tip

想一下y总的神奇比喻：看成男女朋友匹配问题

时间复杂度：最坏情况O(nm)，实际情况下远小于O(nm)

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, M = 200010;
int n1,n2,m;
int h[N],e[M],ne[M],idx;
bool st[N];
int match[N];

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

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] or find(match[j]))
            {
                match[j] = x;
                return true;
            } 
        }
        
    }
    return false;
}

int main()
{
    cin >> n1 >> n2 >> m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
    }
    int res = 0;
    for(int i=1;i<=n1;i++)
    {
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }
    cout << res;
    return 0;
}

搜索与图论

DFS​

BFS​

树的重心​

图的深度搜索​

图的宽度搜索​

图的拓扑序列​

最短路问题​

朴素版Dijkstra算法​

堆优化的Dijkstra算法​

Bellman-Ford算法​

spfa算法​

Fold算法​

最小生成树​

tip

tip

朴素版prim算法​

tip

Kruskal算法​

tip

二分图​

tip

tip

染色法​

tip

匈牙利算法​

tip

DFS

BFS

树的重心

图的深度搜索

图的宽度搜索

图的拓扑序列

最短路问题

朴素版Dijkstra算法

堆优化的Dijkstra算法

Bellman-Ford算法

spfa算法

Fold算法

最小生成树

朴素版prim算法

Kruskal算法

二分图

染色法

匈牙利算法