搜索

2026-06-052026-06-05

突然意识到，最基础最重要的搜索没有整理，都快忘记了，在蓝桥杯前夕复习一下，参加蓝桥杯码蹄杯应该算是我这个菜鸡大学零基础自学算法能触碰到的为数不多的比赛了，无论结果如何，我都很庆幸自己有过这么一段学习经历

dfs

深度优先 要递归

遍历这个点的每个相邻的点

如果这个点没有访问过，

将他标记为访问过

对这个点重复上述过程

auto dfs = [&](auto& dfs, int u) {
  for (auto &v : graph[u]) {
    if (!visited[v]) {
      visited[v] = true;
      dfs(dfs, v);
    }
  }
};
visited[1];
dfs(dfs, 1);

计算树上点到根节点的边权之和

vector<int> dep(n);
auto dfs = [&](auto& dfs, int u, int fa, int deep) {
  dep[u] = deep;
  for (auto [v, w] : g[u]) {
    if (v == fa) continue;
    dfs(v, u, dep + w);
  }
};

bfs

傻傻地以为没缺什么了，结果发现最基础最重要的搜索没有写。。。

要用队列

遍历队顶的点的所有相邻的点 如果没有访问过

插入队列尾部

然后把头部的pop

auto bfs = [&](int start) {
  queue<int> q;
  q.push(start);
  visited[start] = true;
  while (!q.empty()) {
    int u = q.front();
    q.pop()
    for (auto &v : graph[u]) {
      if (!visited[v]) {
        visited[v] = true;
        q.push(v);
      }
    }
  }
};

dijstra

在bfs的基础上用优先队列改进

using pii = pair<int, int>; // dis, u
auto min_dist = vector(n, INT_MAX);
auto calced = vector(n, 0);
priority_queue<pii, vector<pii>, greater<int>> q;
q.emplace(0, 0);
min_dist[0] = 0;
while (!q.empty()) {
  auto &[dis, u] = q.top();
  if (calced[u]) coontinue;
  calced[u] = true;
  if (u == target) return min_dis[u];
  for (auto [v, c] : graph[u]) {
    if (min_dist[v] > dis + c) {
      min_dist[v] = dis + c;
      q.emplace(min_dis[v], v);
    }
  }
}