HW 华为 校招#内推#算法专题：BFS/DFS（内附模板）

• 广度优先搜索算法（英语：Breadth-First-Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。

• 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

• 把根节点放到队列的末尾。
• 每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
• 找到所要找的元素时结束程序。
• 如果遍历整个树还没有找到，结束程序。

#define MAX 100000

int front = 0;/* 头指针 */
int rear = 0;/* 尾指针 */
int round = 0;/* 轮次 */
int queue[MAX] = {0};/* 初始化队列 定义类型根据节点类型指定 */

/* 头节点入队 */
queue[rear] = root;
rear++;

while(front != rear) {
    int step = rear - front;  /* 每一轮要遍历的节点数 */
    for (int i = 0; i < step; i++) {
        /* 新节点入队，可能不止一个节点 */
        queue[rear] = XXX;
        rear++;

        front++;/* 当前节点出队 */
    }
    round++;/* 轮数+1 */
}

• 把根节点压入栈中。
• 每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
• 找到所要找的元素时结束程序。
• 如果遍历整个树还没有找到，结束程序。

int dfs(int stat...) {
    if (is ending) { // 注意搜索的边界状态
        return xx;
    }
    ...//枚举可能的状态
    int result = dfs(stat...); //搜索下一步空间
    ...
    return result;
}