实验8 最小生成树
实验目的
- 掌握图的存储结构
- 掌握图最小生成树的普里姆或克鲁斯卡尔算法及实现
实验内容
- 从文件中读入无向图(网)并以邻接矩阵存储
- 利用普里姆算法构造最小生成树
代码
tu.txt (教程P166 图6.19)
6 10
A B C D E F
A B 6
B E 3
E F 6
F D 2
D A 5
A C 1
B C 5
E C 6
F C 4
D C 5
prim.cpp
#include <iostream>
#include <fstream>
using namespace std;
#define MVNum 10
#define MaxInt 32767 // 表示极大值 ∞
#define GRAPH_FILE "./tu.txt" // 输入的文件路径
using VerTexType = char;
using ArcType = int;
// 辅助数组,用来记录从顶点集U到V-U的权值最小的边
struct
{
VerTexType adjvex; //最小边在U中的那个顶点
ArcType lowcost; //最小边上的权值
} closedge[MVNum];
struct AMGraph
{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
};
// 确定点v在G中的位置
int LocateVex(AMGraph &G, VerTexType v)
{
for (int i = 0; i < G.vexnum; ++i)
if (G.vexs[i] == v)
return i;
return -1;
}
//采用邻接矩阵表示法,创建无向网G
void CreateUDN(AMGraph &G)
{
fstream file(GRAPH_FILE);
if (!file)
{
cout << "没有找到图文件!" << endl;
exit(-1);
}
file >> G.vexnum >> G.arcnum; //输入总顶点数,总边数
for (int i = 0; i < G.vexnum; ++i)
file >> G.vexs[i];
// 初始化邻接矩阵,边的权值均置为极大值 MaxInt
for (int i = 0; i < G.vexnum; ++i)
for (int j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = MaxInt;
// 构造邻接矩阵
for (int k = 0; k < G.arcnum; ++k)
{
VerTexType v1, v2;
ArcType weight;
file >> v1 >> v2 >> weight; //输入一条边依附的顶点
int i = LocateVex(G, v1);
int j = LocateVex(G, v2); //确定v1和v2在G中的位置,即顶点数组的下标
G.arcs[j][i] = G.arcs[i][j] = weight; // 置<v1, v2>的对称边<v2, v1>的权值为w
}
file.close();
}
// 返回还没加入生成树的, 权值最小的点
int Min(AMGraph &G)
{
int index = -1;
int min = MaxInt;
for (int i = 0; i < G.vexnum; ++i)
{
// lowcast == 0 说明这个点已经加入生成树
if ((closedge[i].lowcost != 0) && closedge[i].lowcost < min)
{
min = closedge[i].lowcost;
index = i;
}
}
return index;
}
// 无向网G以邻接矩阵形式存储,从顶点u出发构造G的最小生成树T,输出T的各条边
int MiniSpanTree_Prim(AMGraph &G, VerTexType u)
{
int lowcost_sum = 0;
int start = LocateVex(G, u); // 起点下标
// 初始化辅助数组
for (int i = 0; i < G.vexnum; i++)
{
if (start == i)
closedge[i].lowcost = 0; // 起点加入生成树, 代价是 0(作为加入生成树的标记)
else
closedge[i] = {u, G.arcs[start][i]}; // u 到其它结点 i 的代价为对应权值
}
// 通过 n - 1 轮循环, 把剩下的点加到生成树里面
for (int i = 1; i < G.vexnum; ++i)
{
int k = Min(G); // 找一个没有加入生成树的, 代价最小的点
lowcost_sum += closedge[k].lowcost;
closedge[k].lowcost = 0; // 第k个顶点并入U集(加入生成树)
VerTexType u0 = closedge[k].adjvex; // u0为最小边的一个顶点,u0∈ U
VerTexType v0 = G.vexs[k]; // v0为最小边的另一个顶点,v0∈ V-U
cout << "边 " << u0 << "--->" << v0 << endl; // 输出当前的最小边(u0, v0)
// 现在以 k 为起点, 把和它相邻的没有加入生成树的结点最小代价更新一下
for (int j = 0; j < G.vexnum; ++j)
if (G.arcs[k][j] < closedge[j].lowcost) // 如果结点 j 通过 k 接入生成树的代价 < 之前把 j 加入生成树的最小代价
closedge[j] = {G.vexs[k], G.arcs[k][j]}; // 记录结点 j 的最小代价, 来源边是 k
}
return lowcost_sum;
}
int main()
{
cout << "************算法6.8 普里姆算法**************" << endl;
AMGraph G;
CreateUDN(G);
cout << "无向图G创建完成!" << endl;
cout << "******利用普里姆算法构造最小生成树结果:******" << endl;
VerTexType start = 'A';
int lowcost_sum = MiniSpanTree_Prim(G, start);
cout << "以" << start << "为起点构造最小生成树, 代价为: " << lowcost_sum << endl;
cout << endl;
return 0;
}