图论基础————搜索
DFS 深度优先搜索
原理简述：搜到底为止，不撞南墙不回头。
例题
输出全排列
八皇后问题
BFS 宽度优先搜索
原理简述：层层扩展，广撒网然后慢慢扩展出去。
每次搜到的都是离当前点最近的，具有一个“最短路“的性质。
例题
迷宫
acwing845 八数码问题
在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。
例如：
在游戏过程中，可以把“x”与其上、下、左、右四个方向之一的数字交换（如果存在）。
我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：
例如，示例中图形就可以通过让“x”先后与右、下、右三个方向的数字交换成功得到正确排列。
交换过程如下：
1
2
3
| 1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
|
现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。
输入格式
输入占一行，将3×3的初始网格描绘出来。
例如，如果初始网格如下所示：
1 2 3
x 4 6
7 5 8
则输入为：1 2 3 x 4 6 7 5 8
输出格式
输出占一行，包含一个整数，表示最少交换次数。
如果不存在解决方案，则输出”-1”。
输入样例：
输出样例
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<cstring>
using namespace std;
int n,m;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
int bfs(string start)
{
string end="12345678x";
queue<string> q;
unordered_map<string,int> d;
q.push(start);
while(!q.empty())
{
auto t=q.front();
q.pop();
int dis=d[t];
if(t==end)return dis;
int k=t.find('x');
int x,y;
x=k/3, y=k%3;
for(int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];
if(tx>=0 and ty>=0 and tx<3 and ty<3)
{
swap(t[k],t[tx*3+ty]);
if(!d.count(t))
{
d[t]=dis+1;
q.push(t);
}
swap(t[k],t[tx*3+ty]);
}
}
}
return -1;
}
int main()
{
string start;
for(int i=1;i<=9;i++)
{
char str;
cin>>str;
start+=str;
}
cout<<bfs(start);
return 0;
}
|
树与图的深度优先遍历
例题
acwing846.树的重心
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。
输出格式
输出一个整数m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1≤n≤10^5
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=100050;
int n;
struct node
{
int fr,to,next;
}e[N*2];
int head[N*2];
int vis[N];
int cnt=0;
int ans=N;
void add(int u,int v)
{
e[++cnt].fr=u;
e[cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int dfs(int u)
{
vis[u]=1;
int res=0,sum=1;
for(int i=head[u];i;i=e[i].next)
{
int to=e[i].to;
if(!vis[to])
{
int s=dfs(to);
res=max(res,s);
sum+=s;
}
}
res=max(res,n-sum);
ans=min(ans,res);
return sum;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1);
cout<<ans;
return 0;
}
|
树与图的宽度优先遍历
例题
acwing847.图中点的层次
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
数据范围
1≤n,m≤10^5
输入样例：
输出样例：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=100050;
int n,m;
struct node
{
int to,next;
}e[N];
int head[N],d[N],vis[N];
int cnt=0;
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void bfs()
{
queue<int> q;
q.push(1);
d[1]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int to=e[i].to;
if(d[to]==-1)
{
d[to]=d[u]+1;
q.push(to);
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a, b;
cin>>a>>b;
add(a,b);
}
memset(d,-1,sizeof(d));
bfs();
cout<<d[n];
return 0;
}
|
拓扑序
一些概念：
拓扑序是针对有向图而言的。
入度：有几条边指向这个点（入边）； 出度：有几条出边。
如果图上有环，则不存在拓扑序。因此有向无环图才存在拓扑序，有向无环图（DAG）又称为拓扑图。一个有向无环图一定至少存在一个入度为0的点。
如何求拓扑序：
基于宽搜
- 在拓扑图中，所有入度为0的点都可以作为起点。因此第一步就是先将所有入度为0的点入队。
- 循环：枚举队头的所有出边，u–>v，删掉u–>v的这条边，即d[v]–;
- 如果d[v]==0，就可以入队。完成整个过程就找到了拓扑序。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=100050;
int n,m;
struct node
{
int to,next;
}e[N];
int head[N],d[N],vis[N];
int ans[N];
int cnt=0;
int tot=0;
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
int bfs()
{
queue<int> q;
for(int i=1;i<=n;i++)
{
if(d[i]==0)q.push(i);
}
if(q.empty())return 0;
while(!q.empty())
{
int u=q.front();
ans[++tot]=u;
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int to=e[i].to;
d[to]--;
if(d[to]==0)q.push(to);
}
}
if(tot==n)return 1;
else return 0;
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;
}
if(bfs())
{
for(int i=1;i<=n;i++)
{
cout<<ans[i]<<" ";
}
}
else
{
cout<<-1;
}
return 0;
}
|