基础算法系列——树的入门

树在算法题中非常常见，今天就用一篇文章来入门树的相关知识

目录

树的存储

存储原理

代码模版

树的遍历

1树的深度优先遍历（dfs递归实现）

代码模版 

2树的广度优先遍历（bfs队列实现）

代码模版

关联知识-拓扑排序

拓扑排序是什么

拓扑排序怎么写

---

树的存储

存储原理

可以用邻接矩阵或邻接表，邻接矩阵就是二维数组，邻接表是以链表方式进行存储

代码模版

一个头结点：
所需变量：int h,ne[N],e[N],idx;
解释：h存的是头结点地址，ne[N]存的是每一个节点的下一个节点的地址,(就是数据结构结构体里面的s->next)
e[N]存的是该地址下的值，idx相当于是指针；
具体操作(头插法)：
void cs(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
遍历模版
for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];....}

树的遍历

1树的深度优先遍历（dfs递归实现）
https://www.acwing.com/problem/content/848/

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int h[N],e[N*2],ne[N*2];
int ans=N,idx,n;
bool st[N];
void cs(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{st[u]=1;int sum=1,res=0;for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(st[j])continue;int s=dfs(j);res=max(s,res);sum+=s;}res=max(res,n-sum);ans=min(ans,res);return sum;
}
int main()
{cin >> n;memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b;cin >> a >> b;cs(a,b),cs(b,a);}dfs(1);cout << ans;
}

2树的广度优先遍历（bfs队列实现）

​​​​https://www.acwing.com/problem/content/849/

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],e[N],ne[N],idx;
int d[N];
void cr(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{memset(d,-1,sizeof d);d[1]=0;queue<int>q;q.push(1);while(!q.empty()){int t=q.front();q.pop();for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];if(d[j]==-1){d[j]=d[t]+1;q.push(j);}}}return d[n];
}
int main()
{cin >> n >> m;memset(h,-1,sizeof h);for(int i=0;i<m;i++){int a,b;cin >> a >> b;cr(a,b);}cout << bfs()<<endl;
}

关联知识-拓扑排序

拓扑排序是什么

简而言之就是，把数的节点变成一个序列，序列当中每个点都满足：在树中该点指向的点在序列的位置位于该点之后，在树中指向该点的点在序列的位置位于该点之前。

拓扑排序怎么写

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int h[N],ne[N],e[N],idx;
int d[N],ans[N],cnt;
queue<int>q;
void cr(int a,int b)
{e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool bfspd()
{for(int i=1;i<=n;i++){if(d[i]==0){q.push(i);//把每一个入度为0的点入队}}while(!q.empty()){int t=q.front();q.pop();ans[cnt++]=t;//存储队头的值，队头的值就是入度为零的点for(int i=h[t];i!=-1;i=ne[i]){int j=e[i];d[j]--;//断链，入度-1if(d[j]==0){q.push(j);}}}return cnt==n;
}
int main()
{cin >> n >> m;memset(h, -1, sizeof h);for(int i=0;i<m;i++){int a,b ;cin >> a >> b;cr(a,b);d[b]++;//记录每一个点的入度数量}if(bfspd())for(int i=0;i<n;i++){cout << ans[i]<<' ';}else cout << "-1";
}