GESP 6级客观题｜广度优先搜索 BFS｜课堂讲解

考试频率：低频。本卷共 2 题。

1. 阅读以下广度优先搜索的代码：

void bfs(TreeNode* root) {
   if (root == NULL) {
   return;
   }
   queue<TreeNode*> q;
   q.push(root);
   while (!q.empty()) {
       TreeNode* current = q.front();
       q.pop();
       cout << current->val << " ";
       if (current->left) {
           q.push(current->left);
       }
       if (current->right) {
           q.push(current->right);
       }
   }
}

使用以上算法遍历以下这棵树，可能的输出是（ ）。

     1
    / \
   2   3
  / \   \
 8   9   6
    / \   \
   4   5   7
          / \
         10 11

{{ select(1) }}

• 1 2 8 9 4 5 3 6 7 10 11
• 1 2 3 4 5 6 7 8 9 10 11
• 1 2 3 8 9 6 4 5 7 10 11
• 1 2 3 8 9 4 5 6 7 10 11

2. 使用邻接表存储一个含 $n$ 个顶点、$m$ 条边的图，BFS 遍历的时间复杂度通常是（ ）。

   {{ select(2) }}

• $O(n)$
• $O(m)$
• $O(n+m)$
• $O(nm)$