作业帮根据Prim算法,求图示的最小代价生成树.设①为起点,要求画出构造过程.
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/02 19:18:55
根据Prim算法,求图示的最小代价生成树.设①为起点,要求画出构造过程.
根据Prim算法,求图示的最小代价生成树.设①为起点,要求画出构造过程.
根据Prim算法,求图示的最小代价生成树.设①为起点,要求画出构造过程.
#include
#include
using namespace std;
#define MAX_VERTEX_NUM 10 //最大顶点个数
#define INFINITY 1000 //定义最大值为1000
typedef char VerType;//定点向量
typedef int VRType;//定点之间的关系（即权值）
typedef struct
{
VerType vexs[MAX_VERTEX_NUM]; //顶点向量
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}mgraph, * MGraph;
typedef struct
{
VerType adjvex;
VRType lowcost;
}closedge[MAX_VERTEX_NUM];//记录从顶点集U到V-U的代价最小的边的辅助数组定义
//初始化图
void init_mgraph(MGraph &g)
{
g=(MGraph)malloc(sizeof(mgraph));
g->vexnum=0;
g->arcnum=0;
for(int i=0;ivexs[i]=0;
for(i=0;ich2>>weight;
for(int j=0;jvexnum;j++)
{
if(g->vexs[j]==ch1)
{
row=j;
}
if(g->vexs[j]==ch2)
{
col=j;
}
}
g->arcs[row][col]=weight; //有向带权图只需把1改为weight
g->arcs[col][row]=weight;
}
}
void creat_mgraph(MGraph &g) //创建图
{
add_vexs(g); //增加顶点
add_arcs(g); //增加边
}
void print_mgraph(MGraph &g) //打印图
{
for(int i=0;ivexnum;i++)
cout