2.树与图的遍历、拓扑排序
树和图的存储
首先，树是一种特殊的图（无环连通图）。所以，这里只说图的存储即可。
首先，图分为2种，有向图和无向图。
有向图中2个点之间的边是有方向的，比如
a -> b，则只能从a点走到b点，无法从b点走到a点。无向图中2个点之间的边是没有方向的，比如
a - b，则可以从a走到b，也可以从b走到a通常，我们可以将无向图看成有向图。比如上面，对a到b之间的边，我们可以建立两条边，分别是a到b的，和b到a的。
所以，我们只需要考虑，有向图如何存储，即可。通常有2种存储方式:
邻接矩阵
用一个二维数组来存，比如g[a,b]存储的就是a到b的边。邻接矩阵无法存储重复边，比如a到b之间有2条边，则存不了。（用的较少，因为这种方式比较浪费空间，对于有n个点的图，需要n2的空间，这种存储方式适合存储稠密图）
邻接表
使用单链表来存。对于有n个点的图，我们开n个单链表，每个节点一个单链表。单链表上存的是该节点的邻接点（用的较多）
(一)深度优先遍历DFS
实现有向图，再通过设置两点之间相互指向就实现了无向图，而树是一种特殊的图，即无环连通图，因此实现有向图就可以解决绝大多数问题，一般有邻接矩阵和邻接表两种实现方式，常用邻接表（与哈希类似）
AcWing 846.树的重心
题意：如上图，删除结点1后，剩下三个连通块，最大连通块中点的数量为4；删除结点2后最大连通块点数为6；删除4后最大连通块点数为5…以此类推，最后得到这些数当中的最小值，该结点即为重心
**实现思路：**用深度优先遍历
- 图采用邻接表存储，设置数组h[]，h[i]存储结点i的第一个相邻点(子结点)的下标，初始值为-1。以此构成每个h[i]都指向一条链表，采用头插法实现插入结点
- 图的深度优先遍历：设置一个数组st[i]，表示结点i是否被访问过，每个结点仅被访问一次。访问每个结点，然后访问这个结点所连结的未访问的点，再以这个点为对象递归向下访问其连接的未访问的点（以访问链表的形式进行访问）
- 如何求某个结点删除后的最大连通块中的点数？以当前结点，分向下、向上两部分来计算比较
- 求当前结点向下的最大连通块中结点数：遍历访问当前结点的每个子树，记录该结点的子树中的具有最多的结点数res。同时记录当前结点及其所有子树的结点数sum（初始化为1即包含当前结点）
- 求当前节点向上的连通块中结点数：即总结点数n-sum；
- 然后两者中取大值：res=max(res,n-sum)，即为删除当前结点后最大连通块的结点数
- 最后比较各删除结点的最大连通块的结点数，取最小值：ans=min(ans,res)，即为重心删除后的最大连通块的结点数
#include <iostream>
#include <cstring>
#inclulde <algorithm>
using namespace std;
const int N=1e5+10;
bool st[N];//判断当前结点是否已被访问
int h[N],e[N],ne[N],idx;//实现链接表 和单链表中的含义一样
int n;
int ans=N;//存储最终结果 因为是选出最小 所以初始化为最大的数
//插入结点 构造邻接表 头插法
void add(int a,int b){//a与b之间建立一条边
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
//返回当前结点及其子树的结点总数
int dfs(int u){
st[u]=true;//先标记一下当前结点被访问
int sum=1,res=0;//sum表示当前结点及其子树的结点总数 初始化为1即先算一个当前结点 res表示删除该节点后的最大连通块的结点数
for(int i=h[u];i!=-1;i=ne[i]){//循环遍历当前结点下的链表
int j=e[i];//由链表获得子结点的值
if(!st[j]){//如果这个子节点没有被访问过
int s=dfs(j);//向下 获得结点及其子树的结点总数
res=max(res,s);//得到当前结点下面的最大连通块结点数
sum+=s;
}
}
res=max(res,n-sum);//与上面的最大连通块比较取大者
ans=min(ans,res);
return sum;
}
int mian(){
cin>>n;
memset(h,-1,sizeof h);//初始化为-1
for(int i=0;i<n-1;i++){//构建n-1条边
int a,b;
cin>>a>>b;
add(a,b);add(b,a);//无向图 添加两条边
}
dfs(1);//随便从一个点开始搜 这里从1开始
cout<<ans;
return 0;
}
(二)宽度优先遍历BFS
AcWing 847.图中点的层次
**实现思路：**权值都相等为1，可以使用广度优先遍历，具有最短路的特性
- 依旧使用邻接表的方式存储图
- 设置一个队列q[]，初始1号结点入队，队列不为空的时候就持续操作，每次处理完一个结点，就入队
- 设置一个数组d[]，表示当前结点与1号结点的距离，初始化为-1，等于-1时表示当前结点还未处理(也就同时充当了访问位true or false)，每次处理完一个结点就+1
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int q[N],d[N];
int h[N],e[N],ne[N],idx;//构造链表
int n,m;
//a和b之间添加边
void add(int a,int b){
e[idx]=b;
h[idx]=h[a];
h[a]=idx++;
}
//返回 1号结点到n号结点的最短路距离
int bfs(){
memset(d,-1,sizeof d);//距离初始化为-1
int hh=0,tt=0;//依旧用数组模拟队列
q[0]=1;//1号节点入队 下标从0开始
d[1]=0;//1号结点到自身的距离为0
while(hh<=tt){//队列不为空
int t=q[hh++];//获得队头元素
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
if(d[j]==-1){//表示该结点还未被访问
d[j]=d[t]+1;//更新距离
q[++tt]=j;//当前结点入队
}
}
}
return d[n];
}
int mian(){
cin>>n>>m;
memset(h,-1,sizeof h);//初始化为-1
while(m--)
{
int a,b;
cin>>a>>b;
add(a,b);//有向图
}
cout<<bfs();
return 0;
}
(三) 宽度优先遍历的应用—拓扑序列
图的宽度优先搜索的应用，求拓扑序（拓扑序是针对有向图的）
- 什么是拓扑序：将一个图的很多节点，排成一个序列，使得图中的所有边，都是从前面的节点，指向后面的节点。则这样一个节点的排序，称为一个拓扑序。
- 若图中有环，则一定不存在拓扑序。
- 可以证明，一个有向无环图，至少存在一个入度为0的点，即一定存在一个拓扑序列。有向无环图，又被称为拓扑图。
对于每个节点，存在2个属性，入度和出度。
- 入度，即，有多少条边指向自己这个节点。
- 出度，即，有多少条边从自己这个节点指出去。
每次以入度为0的点为突破口进行处理，每次处理得到一个新的入度为0的点，继续处理
AcWing 848.有向图的拓扑序列
**实现思路：**采用广度优先遍历
- 依旧使用邻接表存储图
- 设置一个数组d[]，表示当前结点的入度，每次添加边就要更新
- 设置一个队列，将入度为0的点入队，初始遍历所有结点将入度为0的点加入队列
- 然后队列不为空的时候取出队头元素，枚举队头元素的所有出边，然后删除，则指向结点的入度要减1，假如指向的节点入度刚好减为0了，则入队。然后继续处理
#include <iostream>
#include <cstring>
using namespace std;
const int N=1e5+10;
int q[N],d[N],h[N],e[N],ne[N],idx;
int n,m;
//ab添加边 构建邻接表
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
//拓扑排序 返回是否存在这个序列
bool topsort(){
int hh=0,tt=-1;
for(int i=1;i<=n;i++)
if(!d[i]) q[++tt]=i;//遍历入队所有入度为0的点
while(hh<=tt){
int t=q[hh++];//队头元素出队
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];
d[j]--;//入度-1
if(!d[j]) q[++tt]=j;//入度为0就入队
}
}
return tt==n-1;//若存在拓扑序列
}
int mian(){
cin>>n>>m;
memset(h,-1,sizeof h);
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
d[b]++;//b的入度加1
}
if(topsort()){//存在拓扑序列 实际就是队列中的数据
for(int i=0;i<n;i++) cout<<q[i]<<" ";
puts("");
}else{//不存在输出-1
cout<<-1;
}
}