Prim算法 是找到所有连通树权值之和最小的一个算法

如有多个连通树 之间都有路径，每个路径上有权值
n个顶点 那么需要n-1条路径能使得每个结点都连接上
且这n-1条路径的权值最小
——————
步骤1：
初始化一个 保存相关顶点坐标的数组adjvex[ver]
初始化一个 保存相关顶点和对应边的权值lowcost[ver]

选择一个顶点作为第一个选择点 ，一般为首位置 或 末位置的顶点。这里选择首位置顶点A

步骤2：
初始化两个数组

将A相关的权值存入lowcost[ver] 数组 （若不存在则是INF 是无穷大）
将 lowcost[ver] 的值都设定为A的下标 0

步骤3
进入大循环
{
寻找A相关边权重最小的一个 选定其顶点B
标记顶点B 且记下其位置k

再寻找B周边的权值 且与原数组 lowcost[ver] 的对应位置（因为没有连线 所以是无穷大）相比较 将小的一个选出来 赋予lowcost[ver]
（简单说 就是将被选择的B的相关权重选出来）

然后用adjvex[ver] 在相关权重的位置上记录B的位置

（（最后回到上面的循环 选择和B相关的权重（还是包括A的相关权重 因为位置所选择 并没有被处理掉 这一点很重要）））
}

标注每次被选择之后 都会被标记 不能二次回头被选择

图的构造

#include<iostream>
#include <iomanip>
using namespace std;

typedef char Vertextype;//顶点类型
typedef int Edgetype;//边缘权值
typedef int Status;
#define MAXVER 9//最大顶点数
#define INF 65535//代表无穷
#define NULL 0


typedef struct Graph
{
	Vertextype Ver[MAXVER];
	Edgetype Arc[MAXVER][MAXVER];
	int NumVer, NumEdg;
}MGraph;

Status CreatGraph(MGraph &G)
{
	int i, j, k, w;
	cout << "Please enter the number of verticesof the graph ： " << endl;
	cin >> G.NumVer;
	cout << "Please enter the number of edges the graph ： " << endl;
	cin >> G.NumEdg;
	cout << "Please enter the name of vex : " << endl;
	for (i = 0; i < G.NumVer; i++){
		//cout << "Please enter the NO." << i + 1 << "%d name of vex : " << endl;
		cin >> G.Ver[i];
	}

	cout << "Diagonal infinity ..." << endl;
	for (i = 0; i < G.NumVer; i++)
		for (j = 0; j < G.NumVer; j++)
		{
		G.Arc[i][j] = INF;//简单图  不循环
		//cout << G.arc[i][j] << endl;//不理解为啥是1
		}
	cout << "...Diagonal infinity" << endl;

	for (int k = 0; k < G.NumEdg; k++){//因为具体哪条边存在不一定 所以选择性输入边
		cout << "Enter the subscripts and weights from vertex vi to vertex vj : " << endl;
		cin >> i >> j >> w;
		/*cout << "Please enter the subscript j of the edge : " << endl;
		cin >> j;
		cout << "Please enter the weight from vertex "<<i<<" to vertex "<<j<<" : " << endl;
		cin >> w;*/

		G.Arc[i][j] = w;
		G.Arc[j][i] = G.Arc[i][j];//无向图  边的信息  是对称的  //有向图的话 无需设置

	}
	return 0;
}

Prim算法实现

/*prim算法生成最小生成树*/
//Lowcost数组会一直变化，初始化时是0顶点和其他顶点之间的权值（有连线就是有权值 不然为INF无穷大）
//后面LC数组会记录下被选择权重最小的那个顶点相关的权重

//Adjvex数组也会一直变化  初始化时是都是0
//会记录下顶点相关权重位置
void MinSpanTree(Graph &G)
{
	int min, i, j, k;
	int Adjvex[MAXVER];		//保存相关顶点下标
	int Lowcost[MAXVER];	//保存相关顶点间边的权值

	/*选取一个顶点 加入最小生成树,选择0是方便后面  所以选择头或尾最好*/
	Lowcost[0] = 0;			//标记为0 就是被选择 后续循环不再用该点
	Adjvex[0] = 0;			
	
	/*取Lowcost数组   存放和第一个生成树顶点相关的权值  若不存在 则默认是INF*/
	for (i = 1; i < G.NumVer; i++){
		Lowcost[i] = G.Arc[0][i];		//将和第一个生成树顶点相关的权值依次存入数组
		Adjvex[i] = 0;//初始化都为第一个顶点的坐标
	}


//开始了
//先找出第一个顶点权值最小的那个
//然后将该权值的另外一个顶点标记  且用k记录位置
	for (i = 1; i < G.NumVer; i++){
		min = INF;		//初始化最小权值为INF 
		j = 1, k = 0;	//k用来记录最小权值的边

		while (j < G.NumVer)//从第一个顶点开始寻找
		{
			if (Lowcost[j] != 0 && Lowcost[j] < min)//相当于寻找合法边 进行比较找到最小的一个
			{
				//如果边存在
				min = Lowcost[j];
				k = j;//记录最小权值的边
			}
			j++;
		}

		cout <<k <<"-----"<<Adjvex[k]<< endl;//打印最小权值的位置   但是这个Ad有什么用呢

		Lowcost[k] = 0;//将此位置的顶点标记存入最小生成树的数组中后续将不再被判断  因为顶点走过一次就想
		
		//这里是更新  LC 和Ad   将上面选择的最小的顶点  的相关权值取代之前的LC里面的值      Ad为记录位置
		for (j = 1; j < G.NumVer; j++){//循环所有顶点 
			if (Lowcost[j] != 0 && G.Arc[k][j] < Lowcost[j]){
				//没有标记过的顶点   
				Lowcost[j] = G.Arc[k][j];
				Adjvex[j] = k;
			}
		}

	}
}

主函数

int main()
{
	Graph G;
	CreatGraph(G);
	MinSpanTree(G);
	MaxSpanTree(G);
	system("pause");
	return 0;
}

最大生成树 原理一样 但这里要把没有路径的INF 改为无穷小

void MaxSpanTree(Graph &G)
{
	int max, i, j, k;
	int adj[MAXVER];
	int maxcost[MAXVER];

	maxcost[0] = 0;
	adj[0] = 0;

	//将无路径设置为无穷小
	for (i = 0; i < G.NumVer; i++)
	{
		for (j = 0; j < G.NumVer; j++)
		{
			if (G.Arc[i][j] == INF)
			{
				G.Arc[i][j] = -1;
			}
		}
	}
		

	//初始化

	for (i = 1; i < G.NumVer; i++)
	{
		maxcost[i] = G.Arc[0][i];
		adj[i] = 0;
	}

	for (i = 0; i < G.NumVer; i++)
	{
		max = 0;
		j = 1; k = 0;
		while (j < G.NumVer)
		{
			if (maxcost[j] != 0 && maxcost[j] > max)
			{
				max = maxcost[j];
				k = j;
			}
			j++;
		}

		cout << k << "----" << adj[k] << endl;
		maxcost[k] = 0;//标记
		for (j = 1; j < G.NumVer; j++)
		{
			if (maxcost[j] != 0 && G.Arc[k][j] > maxcost[j])
			{
				maxcost[j] = G.Arc[k][j];
				adj[j] = k;
			}
		}
	}
}