DFS
深度优先搜索，先按一条路径走到底，再回过头来寻找其他路径。dfs最主要的思想就是递归，根据条件是否满足来判断递归是否停止，通过回溯对递归的一些变量进行状态恢复，是后面的递归不受影响，通过剪枝将不必要的递归步骤除去，从而减小时间复杂度。
一个例题：AcWing 843. n-皇后问题
题目描述：任意两个皇后都不能处于同一行、同一列或同一斜线上。(最重要的)
分析：一种做法是按行row进行深搜，当row==n时就表示搜索完成。深搜的大致过程为：从第一行的八列中选取其中的一列作为皇后位置，并将此位置所在的两条对角线，列作标记表示已访问过（需要回溯），然后再递归访问第二行，依次类推直至row==n时结束。
另一种做法：从头到尾依次访问，再棋盘上的每一个点都有访问和不访问两种状态，并对这两种状态进行递归，直至访问到最后。当一层递归状态为皇后总数为n并且行数为n时，表示此次递归成功完成，并进行输出。
第一种做法代码（效率更高）：
#include <iostream>
using namespace std;
const int N = 10;
char op[N][N];
bool col[N], dg[N * 2], udg[2 * N];
int n;
void dfs(int row)
{
if(row == n)
{
for(int i = 0; i < n; i ++ ) cout << op[i] << endl;
cout << endl;
}
for(int i = 0; i < n; i ++ )
{
if(!col[i] && !dg[i + row] && !udg[n - i + row])
{
col[i] = dg[i + row] = udg[n - i + row] = true;
op[row][i] = 'Q';
dfs(row + 1);
op[row][i] = '.';
col[i] = dg[i + row] = udg[n - i + row] = false;
}
}
}
int main()
{
cin >> n;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < n; j ++ )
op[i][j] = '.';
dfs(0);
return 0;
}BFS
宽度优先搜索，按层次进行遍历，可用于求解最短路问题，最核心的就是引入队列（可手写也可用stl），将遍历的数放入队列，到后面再取出此数对此数进行遍历，直至队列为空，表示bfs的结束。
一个例题：AcWing 844. 走迷宫
题目描述：
给定一个 n×m 的二维整数数组，用来表示一个迷宫，数组中只包含 0或 1，其中 0 表示可以走的路，1 表示不可通过的墙壁。 最初，有一个人位于左上角 (1,1） 处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。 请问，该人从左上角移动至右下角(n,m) 处，至少需要移动多少次。 数据保证(1,1) 处和 (n,m) 处的数字为 0，且一定至少存在一条通路。
分析：题目要求最短路径，如果dfs得到的路径不一定是最短的（只是按一条路走到底），而通过bfs是按层次遍历得到的，故到终点也是最短路径，所以使用bfs。先将起点存入队列，对起点进行遍历时考虑到起点的下一层的所有情况（设置方向数组dx={0,1,0,-1},dy={1, 0, -1,0}),将符合要求的下一层的情况放入队列，继续进行循环遍历，直至找到终点。
代码如下：
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int d[N][N], g[N][N];
//通过d数组存储每个节点到根节点的距离
int bfs()
{
queue<PII> q;
q.push({0, 0});
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
while(q.size())
{
auto p = q.front();
q.pop();
for(int i = 0; i < 4; i ++ )
{
int x = p.first + dx[i], y = p.second + dy[i];
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == 0)
{
d[x][y] = d[p.first][p.second] + 1;
if(x == n - 1 && y == m - 1) return d[x][y];
q.push({x, y});
}
}
}
}
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;
return 0;
}树与图的深度优先遍历
树是一种特殊的图（有向无环图），树和图的存储结构有两种邻接矩阵，邻接表，后者更实用，存储无向图时节点a,b，存储a->b和b->a两次，所以只考虑有向图的存储。
构建树和图时通过邻接表的形式建立，通过题目的输入，将一个点指向的所有点存到一个邻接表中。代码如下：
// 对于每个点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);
构建好树和图后再对其进行操作。深度优先遍历代码：
bool st[N];
void 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);
}
}一道例题：AcWing 846. 树的重心
重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
最起初的想法就是遍历每一个节点，找到此节点邻接点所在联通块的最大数量并记录。但此方法会把每个节点遍历很多遍，导致时间复杂度过高，所以考虑到记录节点。如上图4号节点，有递归返回其子节点3和6所在联通块size3和size6的大小（），用size=n-(size3+size6+1)便可到达4的根节点所在联通块大小，并将max（max(size3,size6), size) 得到最大联通块数量。
代码：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
bool st[N];
int n, minn = N;
int e[M], h[N], ne[M], idx;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int a)
{
st[a] = true;
int sum = 1, res = 0;
for(int i = h[a]; 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);
minn = min(minn, res);
return sum;
}
int main()
{
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
dfs(1);
cout << minn << endl;
return 0;
}树与图的广度优先遍历
按层次进行遍历，运用到队列，从一个点开始，遍历其邻接点，并将其邻接点放入队列继续遍历。模板代码如下：
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);
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; // 表示点j已经被遍历过
q.push(j);
}
}
}拓扑排序
一个树或图的拓扑排序，输出的顺序应符合树或图存储结构的正向关系（即指向一致）如下图：
遍历所有节点将符合拓扑排序的节点放入队列（即节点的入度为0），然后遍历队列，每遍历一个节点将其所有出度的尾节点的入度减1，到尾节点的入度为0时将此节点放入队列，并不断循环，以此形式得到的队列顺序即为拓扑排序的顺序。
模板如下：
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;
}
最短路
单源最短路为在图中求一个节点到其余各节点的最短距离，单源最短路问题又分为有负权边和没有负权边的图。
没有负权边（全是正权边）的最短路问题求解分为朴素版Dijkstra(0(n^2))和堆优化版Dijkstrasuanf（mlogn)两种（n代表顶点数， m代表边数），前者适用于稠密图（m远大于n），后者适用于稀疏图（n远大于m）。
- 朴素版Dijkstra算法：存储结构为邻接矩阵(适用于稠密图可增加空间利用)，存储的数据为两节点之间的距离，若两节点不连通则存储正无穷INF。算法思路：外层n次循环，目的是每循环一次就可将一个节点放入已确定最短距离的集合中，第一层内层循环目的是找到距离1号节点最短的节点下标，第二层内层循环目的是在第一层循环的基础上再次更新所有节点到1号节点的距离。模板如下：
int g[N][N]; // 存储各节点之间的距离
bool st[N]; // 存储该节点是否已确定最短距离
int dist[N]; // 存储各节点到1号节点的距离
int Dijkstra()
{
memset(dist, -1, 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] && (t == -1 || dist[t] > dist[j]))
t = j;
}
st[t] = true;
for(int j = 1; j <= n; j ++)
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
return dist[n];
}2 .堆优化版Dijkstra算法 ：存储结构为邻接表，堆优化相对于朴素版在获取距离1号点最近节 点上进行优化由n->logn，算法思路：设置一个队列存储节点（距离1号点的距离和此节点 下标），每次选取队头（距离最近）并对队头的邻接表节点进行更新和入队操作，直到队 列为空。
typedef pair<int, int> PII;
int dist[N];
int e[M], ne[M], w[M], h[N], idx; // 存储邻接表
bool st[N];
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
priority_queue<PII, vector<PII>, greater<PII>> heap; // 优先队列小根堆
heap.push({0, 1});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int index = t.seond, distance = t.first;
if(st[index]) continue;
else st[index] = true;
for(int i = h[index]; i != -1; i = ne[i])
{
int j = e[i];
dist[j] = min(dist[j], dist[index] + distance);
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({dist[j], j});
}
}
}
return dist[n];
}优先队列放入队列一个数据后，在队列外对此数据进行修改，队列内此数据的值不变
有负权边的图求最短路可用bellman-ford算法(O(nm)) (不管什么情况都是nm)和spfa(O(nm)) (最坏为nm一般都达不到nm)算法求解
1. Bellman-ford算法：外层遍历n次，遍历第一次可确定距离1号点边数为1的最小节点，遍历n次可确定距离1号点边数为n的最小节点，内层循环遍历每一条边，对每条边所在节点与1号点的距离进行更新。模板如下
struct{
int a, b, c;
}edges[N];
int bellman()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i ++)
{
for(int j = 1; j <= m; j ++)
{
int a = edges[j].a, b = edges[j].b, c = edges[j].c;
dist[b] = min(dist[b], dist[a] + c);
}
}
if(dist[n] > 0x3f3f3f3f /2 ) return -1; // 距离与1号点远的点也会进行比较，可能会减小
else return dist[n];
}用结构体存储所有边的信息，遍历所有结构体就可相当于遍历所有边，对于有边数限制的最短路问题求解最多就是用bellman算法，可将外层循环的n次进行更改为题意要求的边数进行求解。
2. spfa算法：实际上是对bellman算法的改进，bellman算法对所有边进行更新包括据1号点很远的点，这些都是无意义的更新，spfa对遍历边进行条件限制，实现优化。设置一个队列用于存储节点下标，spfa用邻接表存储，从1号点开始遍历，将有距离更新的节点入队并标记。模板如下：
int e[M], ne[M], h[N], w[M], idx; // 存储邻接表
int dist[N];
int spfa()
{
memset(dist, 0x3f, sizeof dist);
queue<int> q;
q.push(1);
dist[1] = 0;
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];
}
用spfa算法判断是否含有负环，用一个数组cnt来记录到达每一个节点经过多少条边，若有n个节点且没有负环则1号节点到达节点n所经过的边最多为n - 1，若大于n - 1 则说明存在负环。模板和上类似，如下：
int e[M], ne[M], w[i], h[N], idx;
int dist[N];
bool spfa()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
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 false;
if(!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return true;
}多源最短路：即可求图中所有节点任意两节点的最短距离，只可通过floyd算法实现，背过即可，代码如下
// 初始化
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) g[i][j] = 0;
else g[i][j] = 0x3f3f3f3f;
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
//算法结束后g[i][j] 表示i到j的最短距离算法结束后g[i][j] 表示i到j的最短距离
最短树
在一个图中使各点联通的各边权值之和加起来最小的一棵树为最短树。对于稠密图求最短树使用朴素版prim算法(O(n^2))，对于稀疏图求最短树使用kruskal算法(O(mlogm))
prim算法 和朴素版dijkstra算法类似，但是这里每循环一次更新的是其他点到集合的最短距离，不是单独到1个节点的最短距离。模板代码如下
int dist[N]; // 用于存储各点到最小生成树的距离
int g[N][N]; // 存储各点间的距离
bool st[N]; // 用于标记节点是否在最小生成树里
int prim()
{
memset(dist, 0x3f, sizeof dist);
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;
}
st[t] = true;
if(i) res += dist[t];
if(i && dist[t] == INF) return INF; // 表明图不连通 无最小生成树
for(int j = 1; j <= n; j ++)
{
dist[j] = min(dist[j], g[t][j]);
}
}
return res;
}kruskal算法 （算法大致流程可百度）先存储图所有的边，然后对所有边进行排序，从小到大依次取出所有边，判断边的两点是否在一个集合内，不在一个集合内就将它们合到一个集合内（运用到并查集知识），当集合点数为n时，表明最小生成树已生成。用结构体存储所有边，并排序。模板代码如下
int cnt, res;
struct em{
int a, b, c;
bool operator< (const em &C)cosnt{
return c < C.c;
}
}edges[M]; // 存储边
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
} // 寻找祖宗节点， 用于判断两节点是否在同一颗最小生成树上
int kruskal()
{
for(int i = 1; i <= n; i ++) p[i] = i;
sort(edges, edges + m);
for(int i = 1; i <= m; i ++)
{
int a = edges[i].a, b = edges[i].b, c = edges[i].c;
int x = find(a), y = find(b);
if(x != y)
{
p[x] = y;
res += c;
cnt ++;
}
}
if(cnt < n - 1) return INF; // 判断是否形成最小生成树
else return res;
}kruskal算法不用设置bool数组，只用判断两节点的祖宗节点是否在同一颗最小生成树上，在同一颗树上就避免多次相连。
二分图
二分图性质：节点由两个集合组成，且两个集合内部没有边的图。换言之，存在一种方案，将节点划分成满足以上性质的两个集合。如下图：
如果两个集合中的点分别染成黑色和白色，可以发现二分图中的每一条边都一定是连接一个黑色点和一个白色点。二分图不存在奇数环，若存在奇数环则一定不是二分图，从上述性质可证明。
可通过染色法判别一个图是否为二分图（即判断一个图是否含有奇数环），例如第一个节点存储值为1， 与其直接相连的节点存储值为2，以此类推与2相连的值为1，与1相连为2。若从一个节点除法再回到这个节点而再回到这个节点时的值与原来冲突，则表明存在奇数环，表明不是二分图。模板代码如下：
int e[M], ne[M], h[N], idx; // 邻接表存储
int color[N]; // 存储当前点的颜色
bool dfs(int x, int t)
{
color[x] = t;
for(int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if(color[j] == 0)
if(!dfs(j, 3 - t)) return false;
else if(color[j] == t) return false;
}
return true;
}
bool check()
{
memset(color, -1, sizeof color);
bool flag = true;
for (int i = 1; i <= n; i ++ )
if (color[i] == 0)
if (!dfs(i, 1))
{
flag = false;
break;
}
return flag;
}匈牙利算法 求解二分图的最大匹配问题 匹配： 再图论中一个匹配就是一个边的集合，其中任意两条边无公共节点，如图 3、图 4 中红色的边就是图 2 的匹配
最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。匈牙利算法基本思路：遍历左边集合（左右集合都一样最大匹配数都不会超过左右两边节点数）的所有节点，对第一个节点a的右侧邻接点进行判断，若右侧点b空余（即没有进行匹配过）就直接进行两点匹配，若右侧点b已经被匹配，就看看与右侧点已经匹配的点c是否有空余节点可匹配，若与其空闲节点匹配，若没有则不用做改变,就对a节点进行其剩余的邻接点匹配，若其无剩余邻接点则跳过进行下一次遍历。代码如下
int n1, n2, m; // 第一个和第二个集合点的个数
int e[M], ne[M], h[N], idx;
int match[N];
bool st[N];
bool find(int t)
{
for(int i = h[t]; i != -1; i = ne[i])
{
int j = ne[i];
if(!st[j])
{
st[j] = true;
if(match[j] == 0 || find(match[j]))
{
match[j] = t;
return true;
}
}
}
return false;
}
// 判断是否匹配成功进行记录
int res = 0;
for(int i = 1; i <= n1; i ++)
{
memset(st, false, sizeof st);
if(find(i)) res ++;
}