树与图的遍历

先注意

如果你是和我一样的蒟蒻，在查看这篇博客前请查看我的上一篇博客 《邻接表表示树与图》

深度优先遍历

深度优先遍历的实现

深度优先遍历就是在每个点 x 上面对多条分支的时候，任意选择一条边走下去，执行递归，直到回溯至点 x，再考虑走向其他的边

void dfs(int x){ vis[x]=true;//vis即"visit",一个bool变量，记录当前点被访问过 for(itn i=hd[x];i;i=e[i].nxt){//搜索同起点的每一条边 if(vis[e[i].nxt]==true) continue;//此点引出的某一条边的终点已经被访问过 dfs(e[i].nxt);//继续往下搜 } }

时间戳的添加

其实很简单，建立int类型变量ts[100]，并初始化为0； 建立cnt=0； 每当一个点被记录成“被访问过”，cnt++，表示时间流逝 ts[ x ]=cnt;记录点x被访问时的时间

DFS序

也很简单，建立a[200]

注意一定是2n的数量！每一个点会经过两次！！！

在一个点被标记访问时将点的编号存入a 在for循环结束后，DFS结束前，将点的编号再次存入a 对于上面的这幅图，它的DFS序就是： 1 2 8 8 5 5 2 7 7 4 3 9 9 3 6 6 每一个节点 x 恰好出现两次（这就是为什么一定要把 a 数组大小开成2n 我们还可以发现这样一个规律：某个点x在DFS序中的位置分别为l，r，则[l，r]就是以x为根的子树的DFS序

广度优先遍历

使用一个队列来实现广度优先遍历

队列

队列是一种“先进后出”的数据结构。 在这里可以想象一下卫生间使用的卷纸，用完以后是不是有一个纸板做的“小筒”？ 我们现在可以往里面塞一些乒乓球，并且规定：只能从筒的右端往进塞，如果要从筒中取球，只能从筒的左端取 也就是说：先放进去的球会被先取出来 这时候我们可以称队列的左端为“队头”，右端为“队尾”，C++中可以用一个数组和两个变量来实现队列结构。

queue

元素进行多次入队，出队操作后，用于实现队列数组的开头部分的空间就会被严重浪费，所以经常将队列优化为“循环队列”。所谓循环队列，就是将队列首尾连接，看成一个首尾相连的环状结构，只要队列中的元素个数任何时候都不超过环长，那么随着入队和出队的不断进行，元素将在环中不断地移动，不断利用着曾经使用过的空间。C++STL中的queue就是一个循环队列。

queue的定义与操作

queue<int> q; q.push(element);//将element从队尾入队 q.pop();//从队头出队 int x=q.front();//定义x=队头元素 int y=q.back();//定义y=队尾元素

广度优先遍历的实现

void bfs(){ memset(d,0,sizeof(d)); queue <int> q; q.push(1); d[1]=1; while(q.size()>0){ int x=q.front(); q.pop(); for(int i=hd[x];i;i=edge[i].nxt){ if(d[i]) continue; d[i]=d[x]+1; q.push(i); } } }

不难发现我们在遍历的过程中顺便求出来一个d数组。对于一棵树来讲，d[x]就是点x在树中的深度；而对于一张图来讲，d[x]就是x在图中的层次

最后

遍历是搜索的基础，从名字就可以看出来 遍历其实不难理解，也很好敲