最小生成树的分支顶点的c++代码
时间: 2023-07-22 15:07:57 浏览: 93
最小生成树的分支顶点可以用一个布尔型数组来表示,数组下标表示顶点编号,数组值表示该顶点是否为分支顶点。以下是一个简单的 C++ 代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], w[N], ne[N], idx;
bool st[N]; // st[i] 表示第 i 个顶点是否为分支顶点
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int prim()
{
memset(st, false, sizeof st);
int res = 0;
for (int i = h[1]; i != -1; i = ne[i]) // 从第一个顶点开始
{
int j = e[i];
st[1] = st[j] = true;
}
for (int k = 1; k < n; k ++ )
{
int minv = 1e9, t = -1;
for (int i = 1; i <= n; i ++ )
if (st[i])
for (int j = h[i]; j != -1; j = ne[j])
{
int k = e[j];
if (!st[k] && w[j] < minv)
{
minv = w[j];
t = k;
}
}
if (t == -1) return -1;
st[t] = true;
res += minv;
}
return res;
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c), add(b, a, c);
}
int t = prim();
if (t == -1) puts("impossible");
else cout << t << endl;
return 0;
}
```
在这个实现中,我们将第一个顶点作为初始的分支顶点,然后通过遍历每个分支顶点的相邻边,将其连接的非分支顶点加入分支顶点集合中。当所有顶点都被加入到分支顶点集合中时,算法结束,得到最小生成树。