一般树的遍历和图的遍历的比较

清疚 2021-09-21 07:02 352阅读 0赞

最近在做有关树的题目的时候，很多时候都会遇到要遍历树。这里就不再说关于二叉树的遍历了。具体可以参考一下另一篇博客[二叉树][Link 1]。这里谈一下一般的树的遍历——也就是说一个结点的儿子结点的数目可以大于2。对于这种一般形式的树，常常使用邻接表来存储。也就是可以用`vector<int>Adj`这种形式，这就可以和图联系起来了。

树和图的遍历方式都可以用深度优先搜索（DFS）和广度优先搜索（BFS）来实现。  
用具体的例子来看看树的遍历：（题目链接:[PAT A 1004][]）

*  求树的每层的叶子结点个数

首先知道定义：叶子节点是没有儿子结点的，当我们用邻接表来表示的时候，由 `Adj[i].size()==0`就可以得到结点i就是叶子结点。  
其次，需要记录下每层的叶子结点个数，这就需要求出树的层数，然后用一个数组来记录每层的叶子结点数目。  
有了以上分析，就可以写出代码了：

#include<cstdio>
    #include<algorithm>
    #include<vector>
    using namespace std;
    const int maxn = 110;
    vector<int>Adj[maxn];//存储树
    int nums[maxn]={ 0};//存放每层叶子结点数
    int height = 0; //树的深度
    
    void dfs(int v,int h){ 
    	height = max(height,h);
    	if(Adj[v].size()==0){ 
    		nums[h]++;
    		return ; //到达边界 
    	}
    	for(int i=0; i<Adj[v].size();i++){ 
    		dfs(Adj[v][i],h+1);
    	} 
    }
    
    int main(){ 
    	int n,m ;//结点数和非叶子结点数
    	scanf("%d%d",&n,&m);
    	for(int i=1; i<=m; i++){ 
    		int id,k;
    		scanf("%d%d",&id,&k);
    		for(int j=1; j<=k;j++){ 
    			int temp;
    			scanf("%d",&temp);
    			Adj[id].push_back(temp);
    		}
    	}
    	dfs(1,0);//根节点为01,从第0层开始
    	for(int i=0; i<=height; i++){ 
    		printf("%d",nums[i]);
    		if(i != height){ 
    			printf(" ");
    		}
    	} 
    	return 0; 
    }

树遍历的特点：

*  起点一般固定，是根节点。
 *  不需要另开数组来标志该结点是否已经访问，因为树是不存在环的，并且遍历方向是确定的，一般是从根结点到叶子结点，因此不会走“回头路”。

再来看一下一个图的遍历的例子：（题目链接：[PAT A 1021][]）

*  求一棵树的最大深度  
    貌似是一个和树有关的问题，但是仔细读一下题，要和图结合起来做。首先，由题目给的数据可能无法构成一棵树，这时候需要输出连通块的个数，因此我们可以把它看成一个图，然后求连通块个数，若不为1，则直接输出连通块个数。那为1就是一棵树吗？当然不是，还有可能包含环。而且，这个题需要求出以每个顶点为根节点时数的深度，输出最大深度时的根节点。因此需要按照图的遍历的思想来做。  
    给出参考代码

#include<cstdio>
    #include<vector> 
    #include<algorithm>
    using namespace std;
    const int maxn = 1e4+5;
    vector<int>Adj[maxn];//存储树
    int deep[maxn];//存放以i为根节点的树的高度 
    int max_Deep = 0;
    bool vis[maxn] ={ false};
    
    //先判断是否是连通的
    void dfs(int v){ 
    	vis[v]=true;
    	for(int i=0; i<Adj[v].size();i++){ 
    		int u = Adj[v][i];
    		if(vis[u]==false){ 
    			dfs(u);	
    		}
    	}
    }
    
    //计算树的最大高度
    void DFS(int root,int h){ 
    	max_Deep = max(max_Deep,h);
    	vis[root]=true;
    	for(int i=0; i<Adj[root].size();i++){ 
    		int u = Adj[root][i];
    		if(vis[u] == false){ 
    			DFS(u,h+1);	
    		}
    		
    	}
    }
    
    int main(){ 
    	int n;
    	scanf("%d",&n);
    	for(int i=0; i<n-1; i++){ 
    		int index,next;
    		scanf("%d%d",&index,&next);
    		Adj[index].push_back(next);
    		Adj[next].push_back(index);
    	}
    	//先判断是否连通
    	int k = 0;
    	for(int i=1; i<=n; i++){ 
    		if(vis[i]==false){ 
    			dfs(i);
    			k++;
    		}
    	}
    	if(k != 1){ 
    		printf("Error: %d components",k);
    	}else{ 
    		for(int i=1; i<=n; i++){ 
    			fill(vis,vis+maxn,false);
    			DFS(i,0);
    			deep[i] = max_Deep;
    			max_Deep = 0;
    		}
    		//求出最大深度
    		max_Deep = *max_element(deep+1,deep+n+1);
    		for(int i=1; i<=n; i++){ 
    			if(deep[i]==max_Deep){ 
    				printf("%d\n",i);
    			}
    		}
    	} 
    	return 0;
    }

需要注意的是：  
因为可能存在环，因此需要设置一个数组vis\[maxn\]来标志该顶点时候已经访问了。  
双向性的问题：因为要将每一个顶点作为根节点来遍历一次，因此在输入数据的时候要注意这相当于无向图。即u->v可达，则也设v->u可达。即Adj\[v\].push\_back(u)后需要设置Adj\[u\].push\_back(v)。  
注意每次遍历一次后要将max\_Deep设置0，并且将所有顶点都设置为没有访问false.

[Link 1]: https://blog.csdn.net/iczfy585/article/details/104642999
[PAT A 1004]: https://pintia.cn/problem-sets/994805342720868352/problems/994805521431773184
[PAT A 1021]: https://pintia.cn/problem-sets/994805342720868352/problems/994805482919673856