这样来看，DFS和BFS各有自己的应用场景，但部分场景是重合的。
广度优先搜索可认为是个慢性子，每次搜索到一个节点，他不着急往下走，而是层序完他的所有临接节点。
深度优先搜索可认为是个急性子，每次搜索到一个节点，他会马不停歇地继续走，直到走不通为止。
如果单纯是对树或者图的搜索，两种方式都可以。
BFS擅长求最短路径，DFS擅长递归和回溯；
//Dfs的伪代码
// 1. u表示节点，初始化每个节点状态为未访问
for (auto u: AllNodes) {
u.status = NONE;
}
// 2. 对每个节点进行访问，前驱子图形成由多颗树所形成的森林（每个树的根节点为u）
// u选择的顺序不同，生成的森林不同，树的数目也不同
for (auto u : AllNodes) {
if (u.status == NONE) { //一个节点不可能是在两颗树上，这里必须做剪枝
Dfs(u);
}
}
// 3. 对每颗树进行深度搜索的递归逻辑
//3.1 每个节点有两个时间属性，一是第一次被发现的时间点，一是其邻接链表访问完成时间点
void Dfs(node u)
{
u.status = VISITING;
for (auto v : edges[u]) {
// 访问过的节点不能再递归访问？（可以这么理解，每个节点的两个时间属性是唯一的，不能修改）
// 如果存在环，递归访问，造成死循环
if (v.status == NONE) {
Dfs(v);
}
}
u.status = VISITED;
}以零钱兑换为例子，这个题本质上是求一个n叉树的最小深度，即求最短路径问题。
按照这样的思考方式，可以用BFS来做，BFS的代码如下：
int coinChange(int* coins, int coinsSize, int amount)
{
g_queue.front = 0;
g_queue.tail = 0;
if (amount == 0) {
return 0;
}
for (int i = 0; i <= amount; i++) {
g_visit[i] = false;
}
qsort(coins, coinsSize, sizeof(int), Comp);
InQueue(amount, 0);
int ans = INT_MAX;
while (IsQueueEmpty() == false) {
Item curr = OutQueue();
for (int i = 0; i < coinsSize; i++) { //一个根节点的n个子节点
if (curr.amout < coins[i]) {
break;
}
if (curr.amout == coins[i]) {
ans = fmin(ans, curr.step + 1);
break;
}
int nextAmout = curr.amout - coins[i];
if (g_visit[nextAmout] == true) {//注意要剪枝
continue;
}
InQueue(curr.amout - coins[i], curr.step + 1);
g_visit[nextAmout] = true;
}
}
return ans == INT_MAX ? -1 : ans;
}如果按照树递归的思考方式，那么Dfs的代码如下：
//如果有返回值，那么取个有意义的名字，而不是Dfs，表示当前问题规模的解
int DfsMinCoinsNum(int amout)
{
if (amout == 0) { //递归的出口
return 0;
}
if (g_memBook[amout] != -1) {
return g_memBook[amout];
}
int currAns = INT_MAX;
int subAns = INT_MAX;
for (int i = 0; i < g_coinSize; i++) {
if (amout < g_coins[i]) {
continue;
}
//递归都是假定子问题是可以解决，并且可以正确解决
int temp = DfsMinCoinsNum(amout - g_coins[i]);
if (temp == INT_MAX) {
continue;
}
subAns = fmin(subAns, temp);
}
//如果子问题无解，那么根节点的问题也是无解
g_memBook[amout] = (subAns == INT_MAX) ? INT_MAX : subAns + 1;
return g_memBook[amout];
}评论 (6)
