7.5 对无向带权图,1)写出它的邻接矩阵,并按普里姆算法求其最小生成树;2)

来源:百度知道 编辑:UC知道 时间:2024/06/30 09:17:53
这题要怎么做啊

struct {
VertexType adjvex; // U集中的顶点序号
VRType lowcost; // 边的权值
} closedge[MAX_VERTEX_NUM];
void MiniSpanTree_P(MGraph G, VertexType u) {
//用普里姆算法从顶点u出发构造网G的最小生成树
k = LocateVex ( G, u );
for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化
if (j!=k)
closedge[j] = { u, G.arcs[k][j].adj };
closedge[k].lowcost = 0; // 初始,U={u}
for (i=1; i<G.vexnum; ++i) {//选择其余n-1个顶点

}
}
思想:在生成树的构造过程中,图中 n 个顶点分属两个集合:已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ,则应在所有连接U中顶点和V-U中顶点的边中选取权值最小的边。