Kruskal算法和Prim算法()

这两个算法都是求最小生成树的算法,这里有个模板题
P3366 【模板】最小生成树

Kruskal算法与Prim算法相比比较好理解,基于贪心的思想,每次选取不会产生圈(重边)的权值最小的边,直到所有顶点连通。

Kruskal算法与Prim算法相比比较好理解,基于贪心的思想,每次选取不会产生圈(重边)的权值最小的边,直到所有顶点连通。

Kruskal

具体做法:

  • 将所有顶点看成一个独立的集合
  • 将边按权值从小打到进行排序
  • 利用并查集进行分组,如果一个边使得俩个顶点集合联通,那么就把这俩集合分成一组
  • 直到所有顶点都属于一个集合

如果读者不会并查集,请先去学习并查集再来学最小生成树

如果读者不会并查集,请先去学习并查集再来学最小生成树

这里使用的使优先队列,使用sort也是可以的,重写一下\(compare\)函数即可

  • 创建一个小根堆,把所有边放入堆中,那么堆顶便是权值最小的边。
  • \(ans\)为题目结果,cnt为有多少边被使用,最小生成树的边为\(n-1\),其中\(n\)为顶点个数
  • 从堆顶获取最小的边,判断这个边所对应的俩顶点\((from,to)\)是否在同一组,不在同一组就把他俩合并到同一组里,然后\(++cnt\)并且更新\(ans\)的值
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
struct vertex {
  int from, to, cost;
  bool operator<(const vertex& v) const { return this->cost > v.cost; }
};
  priority_queue<vertex> que;
  ufr(i, 1, M) que.emplace(vs[i]);
  int ans = 0, cnt = 0;
  while (!que.empty()) {
    vertex ver = que.top();
    que.pop();
    if (!same(ver.from, ver.to)) {
      ans += ver.cost;
      ++cnt;
      unit(ver.from, ver.to);
    }
  }

最后一步判断是否可以生成一个最小生成树,就是判断\(cnt\)与\(n-1\)是否相等

Prim

这里存图使用了链式前向星
prim算法与Dijkstra算法比较相似,步骤:

这里存图使用了链式前向星
prim算法与Dijkstra算法比较相似,步骤:

  • 创建一个\(dis\)数组,,表示最小生成树的起点\(s\),值代表最小生成树中以该顶点为终点的边的权值,初始值设置成无穷大。
  • 更新以\(s\)为起点的边,并将以这些边为终点的顶点,然后标记s已经访问过(这里跟Bellman Ford中遍历比较相似),更新其在\(dis\)数组中值。
  • 然后循环遍历,在\(dis\)数组中找一个没访问过,并且在最小生成树中权值最小的顶点(说人话就是没访问过,并且在\(dis\)数组中值最小的索引值)
  • 重复上面的步骤,直到所有顶点都访问过或者无顶点可以访问

解释一下各变量的意思:

\(now\)就是本次访问的顶点,根据上面的说明,就是当前在最小生成树中,为访问的顶点,并且以该顶点(\(now\))为终点的边比以其他未访问过的顶点为终点的边都小

  • \(now\)就是本次访问的顶点,根据上面的说明,就是当前在最小生成树中,为访问的顶点,并且以该顶点(\(now\))为终点的边比以其他未访问过的顶点为终点的边都小

\(ans\)答案,\(tot\)总共已经访问了几个顶点,顶点最多就只能访问N次,所以。

  • \(ans\)答案,\(tot\)总共已经访问了几个顶点,顶点最多就只能访问N次,所以while(tot++ < N)。

\(visited\)数组代表访问过哪些点,\(dis\)数组代表在最小生成树中以索引为终点的边的最小权值

  • \(visited\)数组代表访问过哪些点,\(dis\)数组代表在最小生成树中以索引为终点的边的最小权值

每次循环都要选择一个顶点,而\(minn\)就代表以那个顶点为终点的边的最小权值,如果一次遍历\(minn==inf\)说明没找到,那么首先\(tot\)没到\(N\),说明处理的顶点少于\(N\),并且没顶点处理了,说明无法生成最小生成树

  • 每次循环都要选择一个顶点,而\(minn\)就代表以那个顶点为终点的边的最小权值,如果一次遍历\(minn==inf\)说明没找到,那么首先\(tot\)没到\(N\),说明处理的顶点少于\(N\),并且没顶点处理了,说明无法生成最小生成树
#define goto(x, y) x + 1, x + y + 1
#define mm(x, y) memset(x, y, sizeof(x))
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
struct {
  int to, w, next;
} edge[MAX_N << 1];
int head[MAX_N], cnt = 0;

int dis[MAX_N];
bool visited[MAX_N];

  fill(goto(dis, N), inf);
  mm(visited, 0);
  int tot = 0, now;
  ll ans = 0;
  dis[1] = 0;
  while (tot++ < N) {
    int minn = inf;
    ufr(i, 1, N) if (!visited[i] && minn > dis[i]) {
      minn = dis[i];
      now = i;
    }
    if (minn == inf) {
      f.pts("orz").ln();
      return;
    }
    visited[now] = true;
    ans += minn;
    for (int i = head[now]; i; i = edge[i].next) {
      if (!visited[edge[i].to] && dis[edge[i].to] > edge[i].w)
        dis[edge[i].to] = edge[i].w;
    }
  }

小根堆优化Prim

————————

这两个算法都是求最小生成树的算法,这里有个模板题
P3366 【模板】最小生成树

Kruskal算法与Prim算法相比比较好理解,基于贪心的思想,每次选取不会产生圈(重边)的权值最小的边,直到所有顶点连通。

Kruskal算法与Prim算法相比比较好理解,基于贪心的思想,每次选取不会产生圈(重边)的权值最小的边,直到所有顶点连通。

Kruskal

具体做法:

  • 将所有顶点看成一个独立的集合
  • 将边按权值从小打到进行排序
  • 利用并查集进行分组,如果一个边使得俩个顶点集合联通,那么就把这俩集合分成一组
  • 直到所有顶点都属于一个集合

如果读者不会并查集,请先去学习并查集再来学最小生成树

如果读者不会并查集,请先去学习并查集再来学最小生成树

这里使用的使优先队列,使用sort也是可以的,重写一下\(compare\)函数即可

  • 创建一个小根堆,把所有边放入堆中,那么堆顶便是权值最小的边。
  • \(ans\)为题目结果,cnt为有多少边被使用,最小生成树的边为\(n-1\),其中\(n\)为顶点个数
  • 从堆顶获取最小的边,判断这个边所对应的俩顶点\((from,to)\)是否在同一组,不在同一组就把他俩合并到同一组里,然后\(++cnt\)并且更新\(ans\)的值
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
struct vertex {
  int from, to, cost;
  bool operator<(const vertex& v) const { return this->cost > v.cost; }
};
  priority_queue<vertex> que;
  ufr(i, 1, M) que.emplace(vs[i]);
  int ans = 0, cnt = 0;
  while (!que.empty()) {
    vertex ver = que.top();
    que.pop();
    if (!same(ver.from, ver.to)) {
      ans += ver.cost;
      ++cnt;
      unit(ver.from, ver.to);
    }
  }

最后一步判断是否可以生成一个最小生成树,就是判断\(cnt\)与\(n-1\)是否相等

Prim

这里存图使用了链式前向星
prim算法与Dijkstra算法比较相似,步骤:

这里存图使用了链式前向星
prim算法与Dijkstra算法比较相似,步骤:

  • 创建一个\(dis\)数组,,表示最小生成树的起点\(s\),值代表最小生成树中以该顶点为终点的边的权值,初始值设置成无穷大。
  • 更新以\(s\)为起点的边,并将以这些边为终点的顶点,然后标记s已经访问过(这里跟Bellman Ford中遍历比较相似),更新其在\(dis\)数组中值。
  • 然后循环遍历,在\(dis\)数组中找一个没访问过,并且在最小生成树中权值最小的顶点(说人话就是没访问过,并且在\(dis\)数组中值最小的索引值)
  • 重复上面的步骤,直到所有顶点都访问过或者无顶点可以访问

解释一下各变量的意思:

\(now\)就是本次访问的顶点,根据上面的说明,就是当前在最小生成树中,为访问的顶点,并且以该顶点(\(now\))为终点的边比以其他未访问过的顶点为终点的边都小

  • \(now\)就是本次访问的顶点,根据上面的说明,就是当前在最小生成树中,为访问的顶点,并且以该顶点(\(now\))为终点的边比以其他未访问过的顶点为终点的边都小

\(ans\)答案,\(tot\)总共已经访问了几个顶点,顶点最多就只能访问N次,所以。

  • \(ans\)答案,\(tot\)总共已经访问了几个顶点,顶点最多就只能访问N次,所以while(tot++ < N)。

\(visited\)数组代表访问过哪些点,\(dis\)数组代表在最小生成树中以索引为终点的边的最小权值

  • \(visited\)数组代表访问过哪些点,\(dis\)数组代表在最小生成树中以索引为终点的边的最小权值

每次循环都要选择一个顶点,而\(minn\)就代表以那个顶点为终点的边的最小权值,如果一次遍历\(minn==inf\)说明没找到,那么首先\(tot\)没到\(N\),说明处理的顶点少于\(N\),并且没顶点处理了,说明无法生成最小生成树

  • 每次循环都要选择一个顶点,而\(minn\)就代表以那个顶点为终点的边的最小权值,如果一次遍历\(minn==inf\)说明没找到,那么首先\(tot\)没到\(N\),说明处理的顶点少于\(N\),并且没顶点处理了,说明无法生成最小生成树
#define goto(x, y) x + 1, x + y + 1
#define mm(x, y) memset(x, y, sizeof(x))
#define ufr(i, x, y) for (int i = x; i <= y; ++i)
struct {
  int to, w, next;
} edge[MAX_N << 1];
int head[MAX_N], cnt = 0;

int dis[MAX_N];
bool visited[MAX_N];

  fill(goto(dis, N), inf);
  mm(visited, 0);
  int tot = 0, now;
  ll ans = 0;
  dis[1] = 0;
  while (tot++ < N) {
    int minn = inf;
    ufr(i, 1, N) if (!visited[i] && minn > dis[i]) {
      minn = dis[i];
      now = i;
    }
    if (minn == inf) {
      f.pts("orz").ln();
      return;
    }
    visited[now] = true;
    ans += minn;
    for (int i = head[now]; i; i = edge[i].next) {
      if (!visited[edge[i].to] && dis[edge[i].to] > edge[i].w)
        dis[edge[i].to] = edge[i].w;
    }
  }

小根堆优化Prim