记录自己学习数据结构和算法的过程

普里姆算法是以顶点为核心，不断实现“加点”的过程，适合稠密图

首先是头文件，结构定义

#include<iostream> #define Maxvexnum 10 #define MaxInt 10000 using namespace std; typedef char vertextype; typedef int arctype; typedef struct { vertextype vexs[Maxvexnum]; arctype arcs[Maxvexnum][Maxvexnum]; int vexnum, arcnum; }AM_Graph; struct { vertextype data; arctype lowcost; }closedge[Maxvexnum];

closedge[]数组是用来记录与下标结点存在最小权值边的点与权值

接下来就是一些函数的定义

int LocateVex_AM(AM_Graph& g, char vex); void CreateGraph_AM(AM_Graph& g);

已找到最小值的边构成一个连通图A，剩下的边构成另一个图B，Min函数是找到在B中任意一顶点到A中任意一顶点权值最小的B中的那一个顶点，然后把那个顶点从B中拿出，加入到A中去。

int Min(AM_Graph& g) { int sign = -1; int min = MaxInt; for (int i = 0; i < g.vexnum; i++) if (min > closedge[i].lowcost&&closedge[i].lowcost!=0) {//closedge[i].lowcost!=0是要把已经走过的点排除在外 min = closedge[i].lowcost; sign = i; } return sign; }

普里姆算法

尤为重要的是，最后一定要记得更新closedge[]

void minispantree_Prim(AM_Graph& g, char vex) { int a = LocateVex_AM(g, vex); for (int i = 0; i < g.vexnum; i++) //把各个点的最小边上的权值初始化为各点到源点的值,最小边上的另一个顶点为源点 if (i != a)//区分源点与其他点 { closedge[i].data = vex; closedge[i].lowcost = g.arcs[a][i]; } closedge[a].lowcost = 0; for (int i = 1; i < g.vexnum; i++)//此刻i=1 { int k = Min(g); char u = closedge[k].data; char v = g.vexs[k]; cout << u << v << endl; for (int j = 0; j < g.vexnum; j++) if (g.arcs[j][k] < closedge[j].lowcost) { closedge[j].data = g.vexs[k]; closedge[j].lowcost = g.arcs[j][k]; } } }