首先简单回顾一下dfs：在一个图中，首先找到一个点，依次从当前的点直接向未访问过的点进行扩展，如果发现当前点不可扩展了，那么向上返回上一个顶点，再进行搜索，直到所有的点都被访问完。（下面以一颗树为例）访问顺序：1->2->5->8->4->3->9->6->7
bfs：在一个图中，找到一个起点，先把离这个起点距离为1的点全部访问完，再访问距离为2的点...逐层扩展：
存储一个图
存储图可以使用邻接表或者邻接矩阵，但是邻接矩阵会浪费大量的空间，所以一般用的最多的就是邻接表，下面使用数组来模拟：
const int N = 10010;
int h[N], ne[N], e[N], idx; //使用数组模拟链表，h数组中的元素存的是图中的顶点，e数组存放的是节点的编号，ne[i]存的是i下标所对应的节点的下一个节点编号。
void add(int a, int b) { //建立a到b的关系
e[idx] = b; //节点b的编号就是当前的idx
ne[idx] = h[a]; //b指向表头后的元素
h[a] = idx++; //表头指向b，并将idx++
}dfs应用：树的重心
给定一颗树，树中包含n个结点（编号1~n）和n-1条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式：
第一行包含整数n，表示树的结点数。
接下来n-1行，每行包含两个整数a和b，表示点a和点b之间存在一条边。
输出格式:
输出一个整数m，表示重心的所有的子树中最大的子树的结点数目。
数据范围：
\(1\leqslant n\leqslant 10^5\)
输入样例：
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
分析：
首先如果我们删除1这个节点：
则会出现3个连通块，联通块中的点数分别是：3，4，1那么最大的点数就是4了
如果我们删除2这个节点：
会出现3个连通块，联通块中的点数分别是：1，1，6那么最大的点数就是6了
再来，如果我们删除4这个点：
也会出现3个联通块连通块，连通块中的点数分别是5，2，1那么最大的点数就是5了
最后我们只需要对这些最大的点数求一个最小就行了，所以现在的问题被转换成了如何求那个最大的连通块。
由于dfs会把一个点的儿子全部都遍历一遍，所以可以根据这个特性求出子树的大小。还有一种特殊的情况就是当我们删除4这个节点的时候，可以看出，它的顶上还有一坨节点，这个直接求是很复杂的，但是我们可以用所有的节点，减去4这个点所含节点的个数，所以我们在深搜的过程中，还需要保存以当前节点为根的子树的大小。
示例代码如下：
#include<t;iostream>
#include<cstring>
using namespace std;
const int N = 10010;
int h[N], ne[N], e[N], idx, n;
bool vis[N];
int ans = N;
void add(int a, int b) { //添加节点
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int dfs(int k) { //以当前节点k为根的子树
vis[k] = true; //首先标记是这个节点为访问过的
int size = 1, res = 0; //这个节点本身算一个节点，所以size从1开始，res就是存的当前最大连通块中点的个数
for(int i = h[k]; i != -1; i = ne[i]) { //开始搜索每一个有关系的节点
int j = e[i];
if(!vis[j]) {
int s = dfs(j); //保存以j为根的子树的大小
size += s; //当前节点的大小要加上子树的大小
res = max(res, s); //更新最大的连通块
}
}
res = max(res, n - size); //最后还有一种特殊情况就是顶上有一坨的
ans = min(ans, res); //在最大的连通块中，选最小的
return size; //将当前子树的大小返回
}
int main(){
cin >> n;
memset(h, -1, sizeof h);
for(int i = 0; i < n - 1; ++i) {
int a, b;
cin >> a >> b;
add(a, b); //由于是无向图，所以既要建立a和b之间的关系
add(b, a); //也要建立b和a之间的关系
}
dfs(1);
cout << ans << endl;
return 0;
}bfs应用：图中点的层次
给定一个n个点m条边的有向图，图中可能存在重边和自环。
所有边的长度都是1，点的编号为1~n。
请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。
输入格式
第一行包含两个整数n和m。
接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。
输出格式：
输出一个整数，表示1号点到n号点的最短距离。
数据范围：
n和m均为1到10的5次方
输入样例：
4 5
1 2
2 3
3 4
1 3
1 4
输出样例：
1
bfs的特性：层层扩展，所以一个点如果离起点越近，那么它就越早被访问到，所以说bfs是自带最短路特性的，如果要求a点到b点的最短距离，直接bfs就可以求出
示例代码：
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int e[N], ne[N], h[N], idx; //数组模拟效率高
int d[N]; //表示到起点的距离
int n, m;
queue<int> que;
void add(int a, int b) { //加点
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int bfs() {
memset(d, -1, sizeof d); //初始将所有点到起点的距离设置为-1
d[1]= 0; //起点到起点的距离为0，因为后面要用到，所以需要初始化
que.push(1); //将1号点加入队列
while(que.size()) { //只要队列里面还有元素，说明这一层的元素还没有遍历完
int t = que.front(); //保留起点元素
que.pop(); //起点元素被踢出队列，表示已经访问过了
for(int i = h[t]; i != -1; i = ne[i]) { //开始对起点元素扩展，跟他有关的全部加入加入队列
int j = e[i];
if(d[j] == -1) { //如果没有访问过
d[j] = d[t] + 1; //那就在上一个点的基础上加一步
que.push(j); //同时压入队列，准备后面的扩展
}
}
}
return d[n]; //访问完后，直接将第n个元素到起点的距离返回
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
while(m--) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
Comments | NOTHING