深度优先搜索和广度优先搜索

深度优先搜索

可以用这个图来很好的帮助我们理解DFS，DFS是一种枚举所有完整路径来遍历所有情况的搜索方法，可以使用递归来很好的实现DFS，递归式可以理解为：

void PreorderRecursive(Bitree root){
  if (root) {
    visit(root);
    PreorderRecursive(root->lchild); 
    PreorderRecursive(root->rchild); 
  }
}

解决的典型问题
给定一个序列，枚举这个序列的所有子序列，从中选择一个某方面最优的子序列。也可以简化理解为枚举从n个整数中选择k个数的所有方案

具体问题
有n件物品，每件物品的重量为w[i]，价值为c[i]，现在需要选出若干件物品放入一个容量为V的背包中，使得在选入背包的物品重量和不超过容量V的前提下，让背包中物品的价值之和最大，求最大值。
解决思路：对每个物品都有选择或者不选两条路径，因此总共有2的n次方种可选方案，可以用DFS进行遍历，更新maxValue，遍历完成之后即可得到所需结果。

void DFS(int index,int sumW,int sumC){
	if(index == n){
		if(sumW <= V && sumC > maxValue){
			maxValue = sumC;
		}
		return;
	}
	DFS(index+1,sumW,sumC);
	DFS(index+1,sumW+w[index],sumC+c[index]);
} 

广度优先搜索

BFS以同心圆的方式向外扩散，而DFS则是沿着一条线前进的思路

void BFS(int s){
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		//访问队首元素top
		//将top出队 
		//将top的下一层节点中未曾入队的节点全部入队，并设置为已经入队 
	}
}