最小生成树

算法

字数统计: 922阅读时长: 4 min

 2024/03/14 

算法笔记

三个性质

最小生成树是树，其边树等于顶点树减去1，且树内一定不会有环
对给定的图$G(V,E)$，其最小生成树不唯一，但是边权值和一定唯一
最小生成树是在无向图上生成的，因此根节点可以是任意一个节点

求法有Kruskal和prim，都是基于贪心算法

kruskal稀疏图，复杂度主要来源于对边的排序
prim稠密图，复杂度主要来源于顶点

prim算法

基本思想

设置集合S，存放已被访问的顶点，然后每次从集合$V-S$中选择与集合$S$的最短距离最小的一个顶点$u$，访问并加入集合$S$。之后令顶点$u$为中介点，优化所有从$u$能到达的顶点$v$与集合$S$之间的最短距离。

这样执行n次后直到集合已包含所有的顶点，此思想和Dijkstra几乎相等，只是在设计最短距离时使用了集合$S$代替Dijkstra算法中的起点s。

两个要点

集合$S$的实现 => 用一个bool数组vis[]表示顶点是否已经被访问
顶点$V_i$与集合$S$的最短距离 => 用int数组d[]来存放最短距离

代码

邻接矩阵版本

const int inf = 0x3fffffff;
const int maxv = 1000;
bool vis[maxv] = {false};
int n, G[maxv][maxv], d[maxv];

int prim() {
  fill(d.begin(), d.end(), inf);
  d[0] = 0;
  int ans = 0;	// 存放最小生成树的边权值和
  for (int i = 0; i < n; i++) {
    int u = -1, mx = inf;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)	return -1;
    vis[u] = true;
    ans += d[u];
    for (int v = 0; v < n; v++) {
      // v还未访问 && u能到达v && 以u为中介点可以使得v离集合S更近
      if (vis[v] == false && G[u][v] != inf && G[u][v] < d[v]) {
        d[v] = G[u][v];
      }
    }
  }
  return ans;
}

邻接表版本

struct Node {
  int v, dis;
};
vector<Node> Adj[maxv];
int n, d[maxv];
bool vis[maxv] = {false};

int prim() {
  fill(d.begin(), d.end(), inf);
  d[0] = 0;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int u = -1, mx = inf;
    for (int j = 0; j < n; j++) {
      if (vis[j] == false && d[j] < mx) {
        u = j;
        mx = d[j];
      }
    }
    if (u == -1)	return -1;
    ans += d[u];
    for (auto p: Adj[u]) {
      if (vis[p.v] == fasle && p.dis < d[v]) {
        d[v] = p.dis;
      }
    }
  }
  return ans;
}

kruskal算法

采用基于边贪心的策略

基本思想

两个要点

如何判断两个端点在不同的连通块中 => 并查集，查找father数组
如何讲测试便加入最小生成树 => 并查集，将两个集合合并

代码

由于需要判断边的两个端点是否在不同的连通块中，因此百年的两个端点的编号一定是需要的，然后再加上边权

const int MAXV = 110;
const int MAXE = 10010;
struct edge {
  int u, v;
  int cost;
} E[MAXE];

int father[MAXV];
int findFather(int x) {
  int a = x;
  while (father[x] != x) {
    x = father[x];
  }	// 找到顶层 => x
  while (a != father[a]) {	// 路径压缩
    int z = a;
    a = father[a];
    father[z] = x;
  }
  return x;
}
// n是顶点数，m是边数
int kruskal(int n, int m) {
  int ans = 0, cnt = 0;
  for (int i = 0; i < n; i++)
    father[i] = i;	// 并查集初始化
  sort(E.begin(), E.end(), [&](edge a, edge b) {
    return a.cost < b.cost;
  });
  for (auto p: E) {
    int faU = findFather(p.u);
    int faV = findFather(p.v);
    if (faU != faV) {	// 不是一个连通分量
      father[faU] = faV;
      ans += p.cost;
      cnt++;
      if (cnt == n - 1)	break;
    }
  }
  if (cnt != n - 1)	return -1;
  else	return ans;
}

Next Post

回溯
Previous Post

动态规划股票买卖问题

CATALOG

1. 三个性质
2. prim算法
3. kruskal算法