第三讲 搜索与图论
一、DFS、BFS
1.1、DFS：全排列
#include<iostream>
using namespace std;
const int N = 100015;
int q[N],vis[N],n;
void dfs(int step){
if(step > n){
for(int i = 1;i <= n;i++){
cout << q[i] <<' ';
}cout <<endl;
return ;
}
for(int i = 1;i <= n;i++){
if(!vis[i]){
vis[i] = 1;
q[step] = i;
dfs(step + 1);
vis[i] = 0;
}
}
}
int main(){
cin>>n;
for(int i = 1;i <= n;i++){
q[i] = -1;
vis[i] = 0;
}
dfs(1);
return 0;
}
1.2、BFS：最短路
queue <--初始
while queue 不为空
{
t <--队头
拓展 t 向所有邻接点
if(x未被遍历)
queue <-- x;
d[x] = d[t] + 1;
}
1.3、输出最短路径
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef pair<int ,int >PII;
const int N = 110;
int n,m;
int g[N][N];
int d[N][N];
PII q[N * N],p[N][N];
int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int bfs(){
int head = 0,tail = 0;
q[0] = {0,0};//第一个点{0,0}
//队列全部填充为-1
memset(d,-1,sizeof d);
d[0][0] = 0;
while(head <= tail ){
//取出头部元素
auto t = q[head++];
//四个方向走一遍
for(int i = 0;i < 4;i++){
//如果有路的话就把点加入queue中
int x = t.first + dx[i],y = t.second + dy[i];
//d[x][y] = -1 表示当前点未被遍历过
if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){
//加入queue中
d[x][y] = d[t.first][t.second] + 1;
p[x][y] = t;
q[++tail] = {x,y};
}
}
}
int x = n-1, y = m - 1;
while(x || y){
cout << '(' << x << ',' << y <<") <- ";
auto t = p[x][y];
x = t.first;
y = t.second;
}
cout << '(' << 0 << ',' << 0 <<')';
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];
}
}
int sum = bfs();
cout << endl <<sum << endl;
return 0;
}
1.4、八数码-华容道-推箱子
二、树的遍历–图
2.2、树的邻接表存储–拉链法
const int N = 100010,M = N * 2;
//树/图的邻接表
//head
//e[M] 存储所有链表
int h[N],e[M],ne[M],idx;
int n,m;
bool st[N];
void add(int a,int b){
//头插法
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//深度遍历
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);
}
}
}
2.3、树的重心
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 100010,M = N * 2;
//图的邻接表
//head
int h[N],e[M],ne[M],idx;
int n,m;
bool st[N];
int ans = N;
void add(int a,int b){
//头插法
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
/*
思路：
DFS，删除每一个点，找到当前的连通分量中点数最大的，在找到最小的最大连通分量数
*/
//以u为根的子树中点的数量
int dfs(int u){
st[u] = true; // 标记某一点
//从这一点出发
//sum 当前结点数 = 1 当前连通分量最大点数 res = 0
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); // 从s出发走到底可以有多少个点 == j点所在子树的点数
res = max(res,s); // 最大连通分量
sum += s; //sum ： 当前u点出发的 所以子树 的点数和
}
}
/*
res 当前最大值
ans 总的最小的最大值
*/
//n - sum ： 点u之前的子树的点数和
res = max(res, n - sum);
// 最小的最大联通分量
ans = min(ans,res);
//每一次都是算出从u出发后的子树的点数和
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 << ans << endl;
return 0;
}
2.4、BFS 计算数的层次-最短路径
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
queue<int> q;
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int bfs(){
memset(d,-1,sizeof d);
//队列
q.push(1);
d[1] = 0;
while(q.size()){
//队头
int t = q.front();
q.pop();
for(int i = h[t]; i != -1;i = ne[i]){
//从队头出发到邻接点
int j = e[i];
if(d[j] == -1){
//更新路径: +1
//将下一个结点加入队列
q.push(j);
d[j] = d[t] + 1;
}
}
}
return d[n];
}
int main(){
cin >> n >> m;
memset(h,-1,sizeof h);
int a,b;
for(int i = 0;i < m;i++){
cin >> a >> b;
add(a,b);
}
cout << bfs() << endl;
return 0;
}
三、拓扑排序
queue <--所有入度为0的点
while queue 不为空;
t--队头
枚举 t 的所有出边 t --> j
删除 t --> j d[j]--
if (d[j] == 0)
queue <-- j
#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 head = 0,tail = -1;
for(int i = 1;i <= n;i++){
//查找入度不是0的点
if(!d[i]){
q[++tail] = i;
}
}
//队列中存储的点是 入度为 0 的点
while(head <= tail){
//队头
int t = q[head++];
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i]; //从t出发到下一个点
d[j]--; //假设删除点t 那么t-->j 这条路就没了 即j的入度--
if(d[j] == 0){ //如果该点入度为0
q[++tail] = j; //加入队列中
}
}
}
return (tail == 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] << ' ';
}
}else{
cout << -1 << endl;
}
return 0;
}
四、最短路
最短路的问题在于建图，如何确定点、边。
注意，稠密图使用邻接矩阵来存储，稀疏表使用邻接表。判断：稠密图中边的数量e是n方级别的。
4.1、Dijkstra
4.1.1、朴素Dijkstra
Dijkstra算法简单概括为：
已经确定最短路径的点为集合s1，从未被确定【选取】的点的集合s2中。寻找集合s1到集合s2 最近接入点t，更新至s1
从初始点出发，【默认1】，即dist[1] = 0;然后迭代n次，每一次都是寻找未被遍历的，且通过该点的距离更小dist[j] < dist[t] 的点j，再通过该点t更新从1出发到其他点的距离dist[n];
#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;
//已经确定最短路径的点为集合s1，从未被确定【选取】的点的集合s2中。寻找集合s1到集合s2 最近接入点t，更新至s1
for(int i = 0;i < n;i++){
//迭代n次
int t = -1;
for(int j = 1;j <= n;j++){
//遍历每一个点
//如果该点还未遍历 并且 到该点的距离j 更小
//
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;//选取该点
}
}
st[t] = true;
for(int j = 1;j <= n;j++){
//选取了t点后，通过点t更新dist数组
dist[j] = min(dist[j],dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f)return -1;
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
//存在重边 和自环 解决方法：
//保留距离【权重】 最小的边
memset(g,0x3f,sizeof g);
//初始化
// for(int i = 1;i <= n;i++){
// for(int i = 1;i <= n;i++){
// if(i == j){
// g[i][j] = 0;
// }else{
// g[i][j] = INF;
// }
// }
// }
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = min(g[a][b],c);//选取最短路径
}
int t = dijkstra();
printf("%d\n",t);
return 0;
}
4.1.2、堆优化的Dijkstra
在朴素Dijkstra算法中，O(n^2)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int ,int > PII;
const int N = 1e6 + 10;
int h[N],w[N],e[N],ne[N],idx;
int n,m;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1] = 0;
//优先队列 模拟堆
/*
vector
*/
priority_queue<PII,vector<PII>,greater<PII>> heap;//最小堆
heap.push({0,1});//起点
//一个pair{distance,point}
while(heap.size()){
//获取当前最小的【最短】点 s1 --> s2
auto t = heap.top();
heap.pop();
//ver ： 点 distance ： 距离
int ver = t.second,distance = t.first;
if(st[ver]) continue;
st[ver] = true;
//从ver点出发
for(int i = h[ver]; i != -1;i = ne[i]){
int j = e[i];
if(dist[j] > dist[ver] + w[i]){
dist[j] = dist[ver] + w[i];
//通过ver点可以获取更小的路径
heap.push({dist[j],j});
}
}
}
if(dist[n] == 0x3f3f3f3f)return -1;
return dist[n];
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
//去除重边 和 自环
add(a,b,c);
}
int t = dijkstra();
printf("%d\n",t);
return 0;
}
存在负权边：
首先我们要直到为什么Dijksra算法无法处理存在负权边的问题；
结论：由于Dijkstra算法时基于贪心选择策略进行，故在存在负边的情况下，局部最优解不一定时全局最优解。
分析：
在一个图中【如下图】，在使用Dijkstra算法求从1号点到5号点的最短路径（每次选择离源点最短距离的点更新到其他点的距离），故模拟过程：
- 从1号点出发，选取2号点，此时最短路径时1；
- 从2号点出发，选取距离最短点：3号点，此时最短路为1+2=3；
- 从3号点出发，选取6号点，最短路为2+1+2=5；
- 但其实我们知道选取从1-2-4-5-6 这条路才可以取到最短路为1+3+5+-5 = 4
所以我们如何处理存在负权边的图的最短路呢？还是以上图为例子若我们同时对所有边都进行最短路计算的话（松弛），即从1号点出发，不同于Dijkstra算法不选取4号点，而是从1出发到所有的边都进行松弛操作。
4.2、bellman-ford
举例：bellman-ford 其实就是，k=1时表示从起点出发经过一个点
k=2 表示从起点出发经过2个点
依次类推
所以当k=3，表示从起点经过3个点，此时有第4个点，3->4有边，此时需不需要更新dist[4]的值呢？
其实是不需要的，因为k的意思是到多少条边，除此之外的边不需要考虑，故1–>4 即dist[4] == INF
这时候问题就来了，如何dist[4] == INF？ 此时的dist[3]已经被赋值，dist[4] = dist[3] + w[4]
那么就需要在取第3个点之前就保存此时的dist数组，之前的dist数组为 dist[3] == INF
具体步骤：
for n次
for 所有边a,b,w(松弛)
//对所有边都进行松弛操作，
//a-->b 起点到a 和起点到b，也就是说到点a的最短路求出来了那么到点b的最短路也会求出来
dist[b] = min(dist[b] , backup[a] + w[i])
//backup
bellman-ford的时间复杂度是O(n*m)，bellman-ford的实现原理很简单，对n个点，遍历所有的边。
具体实现：
//bellman-ford 解决负权边 n次遍历 m条边
//存在负权边和自环
/*
bellman-ford 其实就是，k==1时表示从起点出发经过一个点
k==2 表示从起点出发经过2个点
依次类推
所以当k==3，表示从起点经过3个点，此时有第4个点，3->4有边，此时需不需要更新dist[4]的值呢？
其实是不需要的，因为k的意思是到多少条边，除此之外的边不需要考虑，故1-->4 即dist[4] == INF
这时候问题就来了，如何dist[4] == INF？ 此时的dist[3]已经被赋值，dist[4] = dist[3] + w[4]
那么就需要在取第3个点之前就保存此时的dist数组，之前的dist数组为 dist[3] == INF
*/
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 540,M = 10010;
int n,m,k;
int dist[N],backup[N];
/*
backup 备份数组
是dist数组的备份
*/
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++){//k次循环代表k条边
memcpy(backup,dist,sizeof backup);//赋值数组
for(int j = 0;j < m;j++){//m条边
int a = edges[j].a , b = edges[j].b, w = edges[j].w;
// 这里更新dist 数组的时候，如果存在更优值，则需要使用复制的backup数组中来赋值
dist[b] = min(dist[b],backup[a] + w);
}
}
//这里 /2 如果1-->n点不可达但是其中一些点可达，那么就会+上一些值
return dist[n];
}
int main(){
int a,b,c;
scanf("%d%d%d",&n,&m,&k);
for(int i = 0;i < m;i++){
scanf("%d%d%d",&a,&b,&c);
edges[i] = {a,b,c};
}
int t = bellman_ford();
if(t > 0x3f3f3f3f / 2){
puts("impossible");
}else{
printf("%d\n",t);
}
return 0;
}
4.3、spfa
在bellman-ford算法中，循环n次，每次都循环m条边，把入度的点的距离更新值最小，但是只有第k次循环的第k条边之前的边有效，其余边都是无效的。故在spfa算法中，采用了邻接表，只对该点的邻接点进行更新。spfa其实是对bellman-ford优化。队列优化。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
/*
spfa采用邻接表，只更新该点的邻边。
st数组与Dijkstra不同，st数组表示的是发生了更新的点地集合。
*/
const int N = 2020,M = 10010;
int h[N],w[N],e[N],ne[N],idx;//邻接表
int n,m;
int dist[N],cnt[N]; // cnt表示到点n的边的长度是多少，如果边长度>=n表示存在环
bool st[N];//st数组与Dijkstra不同
void add(int a,int b,int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa(){
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]){
//与dijkstra类似
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n)return true;
if(!st[j]){
// 如果该点没有在st中，即现在发生了更新的点需要放入队列
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
bool t = spfa();
if(t){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
4.4、多源最短路–Floyd
Floyd其实就是从多个点出发遍历一遍即可。
可以处理负权边，但依旧不能处理负权回路。
d[i,j] k 表示经过k条边 d[k,i,j] === d[k-1,i,k] + d[k-1,k,j]
for(k = 1; k <= n;k++)
for(i = 1;i <= n;i++)
for(j = 1;j <= n;j++)
d[i,j] = min(d[i,j], d[i,k] + d[k,j])
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
/*
floyd
询问 x 到 y 的距离
*/
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(){
scanf("%d%d%d",&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,w;
scanf("%d%d%d",&a,&b,&w);
d[a][b] = min(d[a][b],w);
}
floyd();
while(Q--){
int a,b;
scanf("%d%d",&a,&b);
if(d[a][b] > INF / 2){
puts("impossible");
}else{
printf("%d\n",d[a][b]);
}
}
return 0;
}
五、最小生成树
5.1、Prim
最小生成树 Prim 基于贪心思想,
for( i = 0; i < n;i++ )
t --> (找到集合外 距离最近 的点)
用 t 更新其他点到 集合 的距离
st[t] = true
#include<iostream>
#include<cstring>
#include<algorithm>
/*
最小生成树 Prim 基于贪心思想
dist[i] INF
for( i = 0; i < n;i++ )
t --> (找到集合外 距离最近 的点)
用 t 更新其他点到 集合 的距离
st[t] = true
*/
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;
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;
}
}
if(i && dist[t] == INF)return INF;
if(i)res += dist[t]; // 先累加
//更新点到集合的距离也就是S2到点t的距离
//这个点到集合的距离
for(int j = 1;j <= n;j++){
dist[j] = min(dist[j],g[t][j]);
}
st[t] = true;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b] = g[b][a] = min(g[a][b],c);
}
int t = prim();
if(t == INF)puts("impossible");
else printf("%d\n",t);
return 0;
}
5.2、Kruskal
O(mlogm)
#include<iostream>
#include<cstring>
#include<algorithm>
/*
1、将边 从小到大排序
2、枚举每条边a--b，w
if a b 不连通
将这条边加入集合中
*/
using namespace std;
const int N = 2e5 + 10;
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(){
scanf("%d%d",&n,&m);
for(int i = 0;i < m;i++){
int a,b,w;
scanf("%d%d%d",&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{
printf("%d\n",res);
}
return 0;
}
六、判定二分图
什么是二分图：而非呢图当且仅当图中不含奇数边数环。
由于途中不含奇数环，所以染色过程一定没有矛盾。
6.1、染色法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
/*
染色法
for(i=1;i<=n;i++)
if i未染色
dfs(i,1)
*/
const int N = 1e5 + 10,M = 2*N;
int n,m;
int h[N],e[M],ne[M],idx;
int color[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
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]){
if(!dfs(j,3 - c)){ // 1 2 表示不同的颜色
//j染色失败
return false;
}
}else if(color[j] == c){
//在dfs对j点进行染色后，如果j点颜色跟u点一样也就是发生了毛对
return false;
}
}
return true;
}
int main(){
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
while(m--){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
}
bool flag = true;
//染色
for(int i = 1;i <= n;i++){
if(!color[i]){
// 进入 dfs 可以计算有多少个联通分量
if(!dfs(i,1)){
flag = false;
break;
}
}
}
if(flag){
puts("Yes");
}else{
puts("No");
}
return 0;
}
6.2、匈牙利算法
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int n1,n2,m;
int h[N],e[N],ne[N],idx;
int match[N];
bool st[N];
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//
bool find(int x){
//左边点x 寻找其连接的右边的点
for(int i = h[x];i != -1;i = ne[i]){
int j = e[i];
//如果该点没有被自己选中
if(!st[j]){
st[j] = true;
//如果该点没有被其他人选中
//或者其他人可以选择另外一个点find(match[j])
if(match[j] == 0 || find(match[j])){
match[j] = x;
return true;
}
}
}
return false;
}
int main(){
scanf("%d%d%d",&n1,&n2,&m);
memset(h,-1,sizeof h);
int a,b;
while(m--){
scanf("%d%d",&a,&b);
add(a,b);
}
int res = 0;
for(int i = 1;i <= n1;i++){
//左边某一个点 寻找 右边的点
memset(st,false,sizeof st);
if(find(i)){
res++;
}
}
printf("%d\n",res);
return 0;
}
