一、搜索
1.深度优先搜索（DFS）
AcWing 842. 排列数字
AcWing 843. n-皇后问题
搜索方式：直接搜索到叶节点，再回溯
剪枝：
分为可行性剪枝和最优性剪枝
可行性剪枝：判断当前情况是否合法
最优性剪枝：判断当前情况是不是最优解（与当前出现的最优解进行比较）
2.广度优先搜索（BFS）
AcWing 844. 走迷宫
AcWing 845. 八数码
搜索方式：一层一层搜索，用队列存储每一轮搜到的点
优点：当每条边权重为1时，可以得到最短路径
二、树与图
1.树与图的存储
有向图存储\(i\)到\(j\)一条边
无向图存储从\(i\)到\(j\)和从\(j\)到\(i\)两条边
(1)邻接矩阵
定义\(g[i][j]\)用来表示\(i\)到\(j\)的一条边的权重
适合存储稠密图，存储稀疏图会浪费空间
(2)邻接表
每个节点都创建一条单链表，链表中存储其可以到达的节点（链表内部无序）
创建一条边即在单链表中添加一个元素
const int N=100010,M=N*2;
//h存储每个链表的头，初始化为-1表示空
int h[N],e[M],ne[M],idx;
//创建a->b的边
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
2.树与图的遍历
（1）树与图的DFS
AcWing 846. 树的重心
void dfs(int u){
st[u]=true;//st数组存储当前节点是否被遍历过
for(int i=h[u];i!=-1;i=ne[i]){//遍历链表
int k=e[i];
if(!st[k]) dfs(k);
}
}
（2）树与图的BFS
AcWing 847. 图中点的层次
//用队列存储当前搜到的点
int bfs(){
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[++tt]=j;
}
}
}
return d[n];
}
3.拓扑排序
AcWing 848. 有向图的拓扑序列
bool topsort(){
int hh = 0, tt = -1;
// d[i] 存储点i的入度
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];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}
三、最短路问题
1.Dijkstra
只能做都是正权边的最短路
（1）朴素Dijkstra
AcWing 849. Dijkstra求最短路 I
适合做稠密图的最短路
时间复杂度\(O(n^2)\)
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; 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;
return dist[n];
}
（2）堆优化Dijkstra
AcWing 850. Dijkstra求最短路 II
适合做稀疏图的最短路
时间复杂度\(O(m\log 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(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap;
heap.push({0, 1});// first存储距离，second存储节点编号
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];
}
2.Bellman-Ford
AcWing 853. 有边数限制的最短路
可以做有负权边的最短路
时间复杂度\(O(nm)\)
const int N=510;
const int M=10010;
struct Edge{
int a,b,w;
}edge[M];//结构体存边，朴实无华且枯燥
int dist[N],backup[N];//backup表示上一次迭代结束的状态
int bellman_ford(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
for(int i=1;i<=k;i++){
memcpy(backup,dist,sizeof dist);
for(int j=1;j<=m;j++)
dist[edge[j].b]=min(dist[edge[j].b],backup[edge[j].a]+edge[j].w);
}
if(dist[n]>0x3f3f3f3f/2) return -1;//防止负权影响正无穷的值
else return dist[n];
}
3.SPFA
Bellman-ford算法优化
每次只找可以更改最短路的边
（1）SPFA求最短路
AcWing 851. spfa求最短路
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;
}
}
}
}
return dist[n];
}
（2）SPFA判断负环
AcWing 852. spfa判断负环
bool spfa(){
queue<int> q;
for (int i = 1; i <= n; i ++ ){//全部入队
st[i] = true;
q.push(i);
}
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];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;//抽屉原理
if (!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
4.Floyd
AcWing 854. Floyd求最短路
可用于多源汇最短路（多个询问）
直接将存储\(i\)到\(j\)边权的\(d[i][j]\)变为存储\(i\)到\(j\)的最短路
时间复杂度\(O(n^3)\)
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]);
}
四、最小生成树问题
1.Prim
AcWing 858. Prim算法求最小生成树
基本思想与Dijkstra类似
（1）朴素Prim
类比朴素Dijkstra
适用稠密图最小生成树
时间复杂度 \(O(n^2)\)
const int N=510,INF=0x3f3f3f3f;
int g[N][N];
int n,m;
int dist[N];
bool st[N];
int prim(){
memset(dist,0x3f,sizeof dist);
int cnt=0;
dist[1]=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;
if(dist[t]==INF) return INF;
st[t]=true;
cnt+=dist[t];
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
}
return cnt;
}
（2）堆优化Prim
类比堆优化Dijkstra
一般不用，换用Kruskal
时间复杂度 \(O(m\log n)\)
2.Kruskal
AcWing 859. Kruskal算法求最小生成树
适用稀疏图最小生成树
时间复杂度 \(O(m\log m)\)
const int N=100010,M=200010,INF=0x3f3f3f3f;
int n,m;
int p[N];
int cnt,res;
struct node{ //结构体存边
int a,b,w;
}edges[M];
bool cmp(node a,node b){ //重载小于号使其按权重比较
return a.w<b.w;
}
int find(int x){ //集合合并（并查集相关知识）
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int kruskal(){ //写到main函数里也没问题
for(int i=1;i<=n;i++) p[i]=i;
sort(edges+1,edges+1+m,cmp);
for(int i=1;i<=m;i++){
auto t=edges[i];
int a=t.a,b=t.b,w=t.w;
a=find(a),b=find(b);
if(a!=b){
cnt++;
res+=w;
p[a]=b;
}
}
if(cnt<n-1) return INF;
return res;
}
五、二分图
1.染色法
AcWing 860. 染色法判定二分图
时间复杂度 \(O(n+m)\)
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n,m;
int color[N];
vector<int> q[N];
bool dfs(int u,int c){
color[u]=c;
for(auto x:q[u]){
if(!color[x]) if(!dfs(x,3-c)) return false;
if(color[x]==c) return false;
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
q[a].push_back(b);
q[b].push_back(a);
}
bool flag=true;
for(int i=1;i<=n;i++)
if(!color[i])
if(!dfs(i,1))
flag=false;
if(flag) puts("Yes");
else puts("No");
return 0;
}
2.匈牙利算法
AcWing 861.二分图的最大匹配
时间复杂度最差 \(O(mn)\)，实际运行时间远小于 \(O(mn)\)
int match[N];//match反向存储
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] || find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
|
