#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
;
}
