树与图的深度优先遍历
树与图的深度优先遍历参考这道题:树的重心
代码如下:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=N*2;
int n;
int h[N];//共有n个节点,即代表有n个头节点,
int e[M],ne[M],idx;
int ans=N;
bool st[N];
void add(int a,int b){//b是新节点,a是头节点
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
//这个是邻接表
}
/*我来解释一下这个邻接表,他是以单链表的形式存储的,但是在图中并不是链表的形式,我们用图来模拟一下
比如1->2,1->3,这里1这个顶点连接了2,3这两个顶点,但是储存形式是以链表存储的,但是现实是一个图*/
int dfs(int u){
st[u]=true;//判断有没有走过
int size=0,sum=0;
for(int i=h[u];i!=-1;i=ne[i]){//这个函数从u开始,统计与u相连的顶点个数
int j=e[i];
if(st[j])continue;//判断j是否被用过,如果被用过则调到链表的下一个值
int s=dfs(j);
/*总得来说,dfs函数是统计与该顶点相连的顶点个数,而sum是统计所有联通块的个数*/
size=max(size,s);
sum+=s;
}
size=max(size,n-sum-1);
ans=min(ans,size);
return sum+1;//这个重心子顶点包括u
}
int main(){
cin>>n;
memset(h,-1,sizeof(h));
for(int i=0;i<n-1;i++){//n-1个无向边就是n个点
int a,b;
cin>>a>>b;
add(a,b),add(b,a);//因为是无向边,所以要有两条联通线
}
dfs(1);
cout<<ans;
return 0;
}
这里解决三个问题:
1.树的重心的解释
2.邻接表的创建及含义
3.解题思路以及流程
1.树的重心的解释
重心定义:重心是指树中的一个结点,如果将这个点删除后,剩余各个连通块中点数的最大值最小,那么这个节点被称为树的重心。
例如这里,该树的重心为4,当4被删除之后,上面一部分和下面一部分的联通块中点数的最大值最小。
2.邻接表的创建及含义
这里邻接表储存的是每个节点与它相连的节点的个数,例如这个图
节点1与节点3,4相连,那么以1为头节点的链表就储存1,3,4
若要在某个节点插入节点,则需要这一句代码
void add(int a,int b){//b是需链接节点,a是头节点
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
//这个是邻接表
}
下面解释一下这个代码
另外
memset(h,-1,sizeof(h));
这一句对所有节点的头节点进行初始化,将每个节点的头节点指向-1(null),对链表进行初始化
3.题目思路
该题的重点即如何找出树的重心
这是一部分代码:
for(int i=h[u];i!=-1;i=ne[i]){//这个函数从u开始,统计与u相连的顶点个数
int j=e[i];
if(st[j])continue;//判断j是否被用过,如果被用过则调到链表的下一个值
int s=dfs(j);
/*总得来说,dfs函数是统计与该顶点相连的顶点个数,而sum是统计所有联通块的个数*/
size=max(size,s);
sum+=s;
}
size=max(size,n-sum-1);
ans=min(ans,size);
return sum+1;//这个重心子顶点包括u
size:表示当前顶点 u 的子树中的最大子树大小。在深度优先搜索 (DFS) 的过程中,size 会不断更新,以记录与顶点 u 相邻的子树中节点数量的最大值。
s:表示与当前顶点 u 相邻的顶点 j 的子树大小。在代码中,s 的值通过递归调用 dfs 函数来计算。
sum:表示当前顶点 u 的子树中所有子树大小的总和。在代码中,sum 的值会随着对与顶点 u 相邻的顶点进行递归调用 dfs 函数而累加。
这个可以从上图看出: