Prim算法是任选一顶点作为起始点，从当前已纳入的顶点与未纳入的顶点间的所有路径中找出权最小的一条进行连接，循环直到所有的顶点都被纳入。代码如下：
#include
#include
#include
#include
class graphic {
public:
graphic（int n）{
std::cout 《 "请输入顶点信息" 《 std::endl;
int tmp;
for（int i = 0; i != n; ++i）{
std::cin 》 tmp;
vertexs.push_back（tmp）；
}
for（int i = 0; i != n; ++i）{
paths.push_back（std::vector （n, std:: numeric_limits::max（）））；
paths[i][i] = 0;
}
std::cout 《 "请输入边数：" 《 std::flush;
int sum;
std::cin 》 sum;
int vi, vj, weight;
for（int i = 0 ; i != sum; ++i）{
std::cout 《 "请输入边" 《 （i+1） 《 ":" 《 std:: flush;
std::cin 》 vi 》 vj 》 weight;
paths[vi][vj] = weight;
paths[vj][vi] = weight;
}
}
void prim（）{
int k = 0;
std:: vector vec;
std:: vector adj;
for（size_t i = 0; i != vertexs.size（）； ++i）{
vec.push_back（ paths[0][i]）；
adj.push_back（0）；
}
while（true ）{
int min = std::numeric_limits :: max（）；
for（size_t j = 0; j != vertexs.size（）； ++j）{
if（vec[j] != 0 && vec[j] < min）{
min = vec[j];
k = j;
}
}
if（min < std::numeric_limits :: max（））{
std::cout 《 adj[k] 《 "->" 《 k 《 std::endl;
vec[k] = 0;
}
else{
std::cout 《 "over" 《 std::endl;
break;
}
for（size_t j = 0; j != vertexs.size（）； ++j）{
if（vec[j] && paths [k][j] < vec[j]）{
vec[j] = paths[k][j];
adj[j] = k;
}
}
}
}
private:
std:: vector vertexs;
std:: vector > paths;
};
int main（）{
graphic g（9）；
g.prim（）；
}