Question

某无向网络邻接矩阵：画出这个无向网络,并从顶点1出发,用Prim算法构造它的最小代价生成树,

Answer 1

根据prim算法得到最小生成树,根据图的基本定义,一个有n个点的图,它的最小生成树必定含有n个点,（n-1）条边.

设图G =（V,E）,V为图的点集,E为图的边的集合.其生成树的顶点集合为U

①、令顶点1为最小生成树的第一个顶点,即将顶点1放入U中

②、在所有u∈U,v∈V-U的边(u,v)∈E中找一条最小权值的边,加入生成树.（在不形成环的情况下,否则找下一个权重最小的边）

③、把②找到的边的v加入U集合.如果U集合已有n个元素,则结束,否则继续执行②.