prim最小生成树怎么判断节点有多少个子节点

Prim算法求解最小生成树时，每次选择与当前生成树相连的权值最小的边所连接的节点作为新的生成树节点，因此可以通过记录每个节点被选中的次数来判断它有多少个子节点。具体做法如下：

1. 维护一个数组selected，记录每个节点是否被选中，初始值为false。

2. 选择一个起点节点作为生成树的根节点，将其标记为已选中。

3. 对于每个已选中的节点，遍历它所有的邻居节点，如果邻居节点未被选中，则将其标记为已选中，并记录它的父节点为当前节点。

4. 继续选择与生成树相连的权值最小的边所连接的节点作为新的生成树节点，重复步骤3，直到所有节点都被选中。

5. 最后，根据每个节点的父节点信息，可以构造出一棵以起点节点为根节点的生成树。每个节点的子节点即为它的所有未被选中的邻居节点，可以通过遍历父节点数组来确定每个节点的子节点个数。

注：以上做法是Prim算法的一种变体，称为Prim-Dijkstra算法，它利用Dijkstra算法的思想来实现Prim算法。