[数据结构与算法]PAT A1004题解 bfs写法

简介

刚开始刷算法，当初学深度优先遍历和广度优先遍历的时候，就觉得广度优先遍历逻辑更加清楚、对新手也更友好，因此拿到这一题第一反应也就是bfs，后来看柳神题解发现只有dfs做法，心态小崩，再一看柳神代码行数30+（我的bfs写了60+），心态大崩（日常膜柳妈）。
但这并不意味着bfs算法复杂度更高。
谨贴上代码，以供参考。

题目介绍

题目链接

BFS（c++）

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> v[100];//vector<node>型数组用于存tree
int book[100];//存储每一层叶子节点数 
queue<int> q;//用于bfs的队列 
int depth=0;//层数从0开始 
int numd[100];//每层的节点数 

void bfs(){
	int j=0; //记录该层当前已经遍历了多少个节点 
	while(!q.empty()){
		int head=q.front();
		j++;//该层遍历过节点数++ 
		q.pop();
		
		if(v[head].size()==0){//叶子节点 
			book[depth]++;//对应层叶子节点数++ 
		}else{//如果有孩子节点则加入孩子节点 
			for(int i=0;v[head][i]!=0;i++){//遍历当前队头节点的每一个子节点 
			  	q.push(v[head][i]);//加入队尾 
			  	numd[depth+1]++;// 每加入一个子节点  下一层节点数++ 
			}
		}
		
		if(j>=numd[depth]){
			depth++;//遍历完一层后层数++ 
			j=0;
		}
	}
}

int main(){
	//初始化 
	q.push(1);//根节点入队 
	numd[0]=1;//第0层总有一个根节点 
	//input 
	int n/*节点数*/, m/*非叶子节点数*/, node/*节非叶子点号*/, k/*该非叶子节点的子节点数*/, c/*子节点号*/;
    scanf("%d %d", &n, &m);
    if(n==0){//不处理空树 
    	return 0;
	}
    for(int i = 0; i < m; i++) {
        scanf("%d %d",&node, &k);
        for(int j = 0; j < k; j++) {
            scanf("%d", &c);
            v[node].push_back(c);
        }
    }
    //bfs
    bfs();
	//output
	printf("%d",book[0]);
	for(int i=1;i<depth;i++){
		printf(" %d",book[i]);//注意末尾无空格
	}
	return 0;
}
 

DFS（c++）

DFS写法参考柳神即可，我在柳神代码的基础上加了点注释
（尊重柳神版权 我就只贴一部分啦 完整版指路 柳婼 の blog

void dfs(int index, int depth) {//当前遍历的节点号--index 当前遍历深度--depth
    if(v[index].size() == 0) {//若节点为空
        book[depth]++;//对应层叶子节点数++ 
        maxdepth = max(maxdepth, depth);//更新最大深度(maxdepth 用于 后续book[]的输出 只输出前maxdepth项) 
        return ;//到达边界,返回上一层dfs 
    }
    for(int i = 0; i < v[index].size(); i++)//遍历非叶子节点的每一个子节点 
        dfs(v[index][i], depth + 1);//进入下一层,遍历子节点 
}