算法竞赛专题解析│搜索基础( 二 )


intG=newNode('G');intH=newNode('H');intI=newNode('I');
insert(E,B,0);insert(E,G,1);//E的左孩子是B , 右孩子是G
insert(B,A,0);insert(B,D,1);
insert(G,F,0);insert(G,I,1);
insert(D,C,0);insert(I,H,0);
introot=E;
returnroot;
}
intmain{
introot=buildtree;
queue<int>q;
q.push(root);//从根节点开始
while(q.size){
inttmp=q.front;
cout<<node[tmp].value<<"";//打印队头
q.pop;//去掉队头
if(node[tmp].lchild!=-1)q.push(node[tmp].lchild);//左孩子入队
if(node[tmp].rchild!=-1)q.push(node[tmp].rchild);//右孩子入队
}
return0;
}
作为对照 , 下面给出指针版二叉树代码 。
BFS(指针版二叉树)
#include<bits/stdc++.h>
usingnamespacestd;
structnode{//指针二叉树
charvalue;
node*l,*r;
node(charvalue='https://pcff.toutiao.jxnews.com.cn/p/20210226/#',node*l=NULL,node*r=NULL):value(value),l(l),r(r){}
};
voidremove_tree(node*root){//释放空间
if(root==NULL)return;
remove_tree(root->l);
remove_tree(root->r);
deleteroot;
}
intmain{
node*A,*B,*C,*D,*E,*F,*G,*H,*I;//以下建一棵二叉树
A=newnode('A');B=newnode('B');C=newnode('C');
D=newnode('D');E=newnode('E');F=newnode('F');
G=newnode('G');H=newnode('H');I=newnode('I');
E->l=B;E->r=G;B->l=A;B->r=D;
G->l=F;G->r=I;D->l=C;I->l=H;//以上建了一棵二叉树
queue<node>q;
q.push(*E);
while(q.size){
node*tmp;
tmp=&(q.front);
cout<<tmp->value<<"";//打印队头
q.pop;//去掉队头
if(tmp->l)q.push(*(tmp->l));//左孩子入队
if(tmp->r)q.push(*(tmp->r));//右孩子入队
}
remove_tree(E);
return0;
}
BFS是逐层扩散的 , 非常符合在图上计算最短路径 , 先扩散到的节点 , 离根节点更近 。 很多最短路径算法 , 都是在BFS上发展出来的 。
具体内容 , 请参考本篇参考书《算法竞赛入门到进阶》第10章图论 。
04
DFS的常见操作和代码实现
1.DFS的常见操作
算法竞赛专题解析│搜索基础】DFS的原理 , 就是递归的过程 。
DFS的代码比BFS更简短一些 。 下面给出两个代码 , 分别基于指针版和静态版二叉树 。 它们输出了图1二叉树的各种DFS操作 , 有时间戳、DFS序、树深度、子树节点数 , 另外还给出了二叉树的中序输出、先序输出、后序输出 。
DFS访问节点 , 经常用到以下操作:
(1)节点第一次被访问的时间戳 。 用dfn[i]表示节点i第一次被访问的时间戳 , 函数dfn_order打印出了时间戳:
dfn[E]=1;dfn[B]=2;dfn[A]=3;dfn[D]=4;dfn[C]=5;
dfn[G]=6;dfn[F]=7;dfn[I]=8;dfn[H]=9 。
时间戳就是先序输出 。
(2)DFS序 。 在递归时 , 每个节点会来回访问2次 , 即第1次访问和第2次回溯 。 函数visit_order打印出了DFS序:
{EBAADCCDBGFFIHHIGE}
这个序列有一个重要特征:每个节点出现2次 , 被这2次包围起来的 , 是以它为父节点的一棵子树 。 例如序列中的{BAADCCDB} , 就是B为父节点的一棵子树 , 又例如{IHHI} , 是以I为父节点的一棵子树 。 这个特征是递归操作产生的 。
(3)树的深度 。 从根节点往子树DFS , 每个节点第一次被访问时 , 深度加1 , 从这个节点回溯时 , 深度减1 。 用deep[i]表示节点i的深度 , 函数deep_node打印出了深度:
deep[E]=1;deep[B]=2;deep[A]=3;deep[D]=3;deep[C]=4;
deep[G]=2;deep[F]=3;deep[I]=3;deep[H]=4 。
(4)子树节点总数 。 用num[i]表示以i为父亲的子树上的节点总数 , 例如 , 以B为父节点的子树 , 共有4个节点{ABCD} 。 只需要简单地DFS一次就能完成 , 每个节点的数量等于它的2个子树的数量相加 , 再加1 , 即加它自己 。 函数num_node做了计算并打印出了以每个节点为父亲的子树上的节点数量 。
另外还有树的重心:在一棵中 , 找到一个节点 , 把树变为以该点为根的有根树 , 并且最大子树的结点数最小 。 本文没有给出代码 。
竞赛中一般用静态版二叉树写代码 。 作为对照 , 后面也给出指针版二叉树的代码 。
DFS(静态版二叉树)
#include<bits/stdc++.h>
usingnamespacestd;
constintmaxn=100005;
structNode{
charvalue;
intlchild,rchild;
}node[maxn];
intindex=0;//记录节点
intnewNode(charval){//新建节点
node[index].value=https://pcff.toutiao.jxnews.com.cn/p/20210226/val;
node[index].lchild=-1;//-1表示空
node[index].rchild=-1;
returnindex++;
}
voidinsert(int&father,intchild,intl_r){//插入孩子
if(l_r==0)//左孩子
node[father].lchild=child;
else//右孩子
node[father].rchild=child;