赞
踩
Prim算法的由来
Prim算法利用了MST的性质:假设N= (V,E)是一个连通图,U是顶点集V的一个非空子集,若(u,v)是一条最小权值的边,其中u属于U,v属于V-U,则必存在一颗包含(u,v)的最小生成树。
Prim算法的实现
普里姆算法的实现假设一个无向网G以邻接矩阵形式存储,从顶点u出发构造G的最小生成树T,要求输出T的各条边。为实现这个算法需附设一个辅助数组closedge,以记录从U到V-U具有最小权值的边。。对每个顶点v∈V-U,在辅助数组中存在一个相应分量closedge[i-1],它包括两个域:lowcost和adjvex,其中lowcost存储最小边上的权值,adjvex存储最小边在U中的那个顶点。显然,closedge[i-1].-lowcost=min{cost(u,vi)lu∈U}其中cost(u,v)表示赋于边(u,v)的权。
图例:
//辅助数组结构
typedef struct
{
string adjvex;//最小边在U的那个顶点
int lowcost;//最小边的权值
}closedge[MVNum];
//辅助数组结构
Prim算法步骤
①首先将初始顶点u加入U中,对其余的每一个顶点,将closedge均初始化为到u的边信息。
②循环n-1次,做如下处理:
● 从各组边closedge中选出最小边closedge[k],输出此边;
●将k加入U中;
●更新剩余的每组最小边信息closedgel,对于V-U中的边,新增加了一条从k到j的边,如果新边的权值比closedge.lowcost小,则将closedgelowcost更新为新边的权值。
运行结果
实现代码
(邻接矩阵和邻接表分别实现)
/*邻接矩阵实现 若要邻接表实现,初始化V时,只需将生成树的顶点的邻接边的权值赋给辅助数组,其余的全部辅为maxint 更新最小边时同样如此 */ #include<iostream> #include<string> using namespace std; #define OK 1 #define ERROR 0 #define MAXint 32767 //表示无穷大 #define MVNum 100 //最大顶点数 //邻接矩阵的结构 typedef struct { string vexs[MVNum];//顶点表 int arcs[MVNum][MVNum];//邻接矩阵,也就是表示边的权值 int vexnum, arcnum;//图的顶点数和边的个数 }AMGraph; //邻接矩阵的结构 //邻接表的结构 typedef struct ArcNode {//边结点 int adjvex;//该边所指向的顶点的位置 struct ArcNode* nextarc;//指向下一条边的指针 int info;//和边相关的信息 }ArcNode; typedef struct {//顶点信息 string data; ArcNode* firstarc;//指向第一条依附该顶点的边的指针 }VNode, AdjList[MVNum]; typedef struct//邻接表 { AdjList vertices;//顶点信息 int vexnum, arcnum;//图的当前顶点数和边数 }ALGraph; //邻接表的结构 //查询结点位置 int Locate(AMGraph G, string v) { for (int i = 0; i < G.vexnum; i++) { if (G.vexs[i] == v) { return i; } } return -1; } //查询结点位置 int Locate(ALGraph G, string v)//Locate重载 { for (int i = 0; i < G.vexnum; i++) { if (G.vertices[i].data == v) { return i; } } return -1; } //辅助数组结构 typedef struct { string adjvex;//最小边在U的那个顶点 int lowcost;//最小边的权值 }closedge[MVNum]; //辅助数组结构 //创建邻接矩阵 int CreateUDN(AMGraph& G)//无向图的构造 { cout << "请输入图的顶点数和边数:"; cin >> G.vexnum >> G.arcnum; cout << "请输入各点的信息:"; for (int i = 0; i < G.vexnum; i++) { cin >> G.vexs[i]; } for (int i = 0; i < G.vexnum; i++)//初始化边的权值为MAXINT { for (int j = 0; j < G.vexnum; j++) { G.arcs[i][j] = MAXint; } } cout << "各边的顶点信息和权值:"; for (int k = 0; k < G.arcnum; k++)//构造邻接矩阵 { string v1, v2; int w;//边的两个顶点以及权值 cin >> v1 >> v2 >> w; int i = Locate(G, v1);//找到点的位置 int j = Locate(G, v2); G.arcs[i][j] = w;//赋予权值 G.arcs[j][i] = G.arcs[i][j]; } return OK; } //创建邻接矩阵 //创建邻接表 int CreateUDG(ALGraph& G) { cout << "请输入图的顶点数和边数:"; cin >> G.vexnum >> G.arcnum;//输入顶点数和边数 cout << "请输入各个顶点的信息:"; for (int i = 0; i < G.vexnum; i++)//初始化顶点信息 { cin >> G.vertices[i].data;//输入顶点的信息 G.vertices[i].firstarc = NULL;//firstarc置空 } cout << "请输入各边的顶点信息和权值:"; for (int k = 0; k < G.arcnum; k++) { string v1, v2; int weight;//权值 cin >> v1 >> v2 >> weight;//输入一条边依附的两个顶点 int i = Locate(G, v1); int j = Locate(G, v2); ArcNode* p1 = new ArcNode; p1->info = weight; p1->adjvex = j; p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; ArcNode* p2 = new ArcNode; p2->info = weight; p2->adjvex = i; p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2; } return OK; } //创建邻接表 //找到权值最小的边 int Min(closedge s,int len) { int min = MAXint; int k = -1; for (int i = 0; i < len; i++) { if (s[i].lowcost < min && s[i].lowcost != 0) { min = s[i].lowcost; k = i; } } return k; } //找到权值最小的边 //prim最小生成树算法 void MiniSpanTree_Prim(AMGraph G, string u) { closedge close; int k = Locate(G, u);//k为顶点u的下标 for (int i = 0; i < G.vexnum; i++)//对V-U的每一个顶点vj,初始化close; { if (k != i) { close[i] = { u,G.arcs[k][i] }; } } close[k].lowcost = 0;//初始化U,此时U中只有u一个顶点 for (int i = 1; i < G.vexnum; i++) { k = Min(close,G.vexnum);//找到与u权值最小的边 string u0 = close[k].adjvex;//最小边的一个顶点 string v0 = G.vexs[k];//最小边的另一个顶点 cout << u0 <<"-"<< v0 << endl;//输出最小边 close[k].lowcost = 0;//把此顶点并入U集 for (int i = 0; i < G.vexnum; i++)//新节点并入U后重新选择最小边 { if (G.arcs[k][i] < close[i].lowcost) { close[i] = {G.vexs[k],G.arcs[k][i]}; } } } } //prim最小生成树算法 //prim最小生成树算法 void MiniSpanTree_Prim(ALGraph G, string u) { closedge close; int k = Locate(G, u);//k为顶点u的下标 for (int i = 0; i < G.vexnum; i++) { close[i] = { u,MAXint }; } ArcNode* p = new ArcNode; p = G.vertices[k].firstarc; while (p) { close[p->adjvex] = { u,p->info }; p = p->nextarc; } close[k].lowcost = 0;//初始化U,此时U中只有u一个顶点 for (int i = 1; i < G.vexnum; i++) { k = Min(close, G.vexnum);//找到与u权值最小的边 string u0 = close[k].adjvex;//最小边的一个顶点 string v0 = G.vertices[k].data;//最小边的另一个顶点 cout << u0 << "-" << v0 << endl;//输出最小边 close[k].lowcost = 0;//把此顶点并入U集 ArcNode* arc = G.vertices[k].firstarc; while (arc) { if (arc->info < close[arc->adjvex].lowcost) { close[arc->adjvex] = {G.vertices[k].data,arc->info}; } arc = arc->nextarc; } } } //prim最小生成树算法 /*v1 v2 v3 v4 v5 v6 v1 v2 6 v1 v3 1 v1 v4 5 v3 v2 5 v3 v4 5 v3 v5 6 v3 v6 4 v2 v5 3 v5 v6 6 v4 v6 2 v1*/ int main() { ALGraph G; CreateUDG(G); cout << "您要构造的最小生成树的起点:"; string v; cin >> v; MiniSpanTree_Prim(G, v); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。