数据结构——邻接矩阵的最小生成树Prim算法

时间:2021-06-06 09:55:05
  
  
  
#include < iostream >
#include
< iomanip >
using namespace std;

#define MAX_VERTEX_NUM 10 // 最大顶点个数
#define INFINITY 32768
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 ;i < MAX_VERTEX_NUM;i ++ )
g
-> vexs[i] = 0 ;
for (i = 0 ;i < MAX_VERTEX_NUM;i ++ )
for ( int j = 0 ;j < MAX_VERTEX_NUM;j ++ )
g
-> arcs[i][j] = INFINITY;
}

void add_vexs(MGraph & g) // 增加顶点
{
cout
<< " 请输入顶点的个数: " << endl;
cin
>> g -> vexnum;
cout
<< " 请输入顶点的值 " << endl;
for ( int i = 0 ;i < g -> vexnum;i ++ )
{
cin
>> g -> vexs[i];
}
}
void add_arcs(MGraph & g) // 增加边
{
cout
<< " 请输入边的个数: " << endl;
cin
>> g -> arcnum;
VerType ch1,ch2;
int weight;
int row,col;

for ( int i = 0 ;i < g -> arcnum;i ++ )
{
cin
>> ch1 >> ch2 >> weight;
for ( int j = 0 ;j < g -> vexnum;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 ;i < g -> vexnum;i ++ )
cout
<< " " << g -> vexs[i] << " " ;
cout
<< endl;
for (i = 0 ;i < g -> vexnum;i ++ )
{
cout
<< g -> vexs[i];
for ( int j = 0 ;j < g -> vexnum;j ++ )
{
cout
<< setw( 5 ) << g -> arcs[i][j] << " " ;
}
cout
<< endl;
}
}

// 返回顶点v在顶点向量中的位置
int LocateVex(MGraph & g, VerType v)
{
int i;
for (i = 0 ; v != g -> vexs[i] && i < g -> vexnum; i ++ )
;
if (i >= g -> vexnum)
return - 1 ;
return i;
}
// 求出T的下一个节点,第k节点
int minimun(MGraph & g, closedge closedge)
{
int min = INFINITY,k = 0 ,i;
for (i = 0 ;i < g -> vexnum;i ++ )
{
if (closedge[i].lowcost != 0 && closedge[i].lowcost < min)
{
min
= closedge[i].lowcost;
k
= i;
}
}
return k;
}
// 普里姆算法
void MiniSpanTree_Prim(MGraph & g, VerType u) // 普里姆算法从顶点u出发构造G的最小生成树T,输出T的各条边。
{
closedge closedge;

int i,j;
int k = LocateVex(g,u);
for (j = 0 ;j < g -> vexnum;j ++ ) // 辅助数组初始化
{
if (j != k)
{
closedge[j].adjvex
= u;
closedge[j].lowcost
= g -> arcs[k][j];
}
}
closedge[k].lowcost
= 0 ; // 初始,U={u}

for (i = 1 ;i < g -> vexnum;i ++ ) // 选择其余g.vexnum-1个顶点
{
k
= minimun(g,closedge); // 求出T的下一个节点,第k节点
cout << closedge[k].adjvex << " " << g -> vexs[k] << " " << closedge[k].lowcost << endl; // 输出生成树的边
closedge[k].lowcost = 0 ; // 第k顶点并入U集

for (j = 0 ;j < g -> vexnum;j ++ )
{
if (g -> arcs[k][j] < closedge[j].lowcost) // 新顶点并入集后,选择新的边,将小的边放到辅助数组中
{
closedge[j].adjvex
= g -> vexs[k];
closedge[j].lowcost
= g -> arcs[k][j];
}
}
}
}
// MiniSpanTree_Prim

int main()
{
MGraph G;
init_mgraph(G);
// 初始化图
creat_mgraph(G); // 创建图
print_mgraph(G); // 打印图
MiniSpanTree_Prim(G,G -> vexs[ 0 ]); // 最小生成树

return 0 ;
}