普里姆算法求图(邻接矩阵存储)的最小生成树

本文主要是介绍普里姆算法求图(邻接矩阵存储)的最小生成树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

——图的存储结构为: 邻接矩阵

具体算法思想和过程实现:
请前往B站，观看Up主 : 懒猫老师 的视频

视频1 : 《懒猫老师-数据结构-(42)最小生成树(Prim算法,普里姆算法,普利姆)》

视频2 : 《懒猫老师数据结构-(43)最小生成树(Prim算法的实现,普里姆算法,普利姆)》

视频1传送门
视频2传送门

附上本人实现的代码:
能成功运行，可能会存在有不足的地方，如果有，敬请指出，并多多指教。

// 用邻接矩阵来作为图的存储结构，用来实现求最小生成树。

#include<iostream>
using namespace std;

#define MVNum 100
#define Maxlnt 32767
#define OK 1

class AMGraph;
class AMGraph
{
private:
	char vexs[MVNum];          //定义一个顶点表;
	int arcs[MVNum][MVNum];    //定义一个邻接矩阵;
	int vexnum, arcnum;        // 定义图的当前点数和边数;


public:
	bool creat_graph();         //图的构造函数;
	int Locate_vex(char c);     //定位函数，确定顶点在顶点表当中的位置;
	void print();               //将图的顶点表和邻接矩阵都给打印出来。
	friend void Prim(AMGraph G);

};

//辅助数组中所需要用到的结构体:
typedef struct SE
{
	char adjvex;
	int lowcost;  //最小生成树中边所对应的最小权值;
};

int AMGraph::Locate_vex(char c)
{
	for (int i = 0; i < vexnum; i++)
	{
		if (c == vexs[i]) return i;
	}
	return -1; // -1表示顶点不存在顶点表当中;
}

bool AMGraph::creat_graph()
{
	cout << "请依次输入总顶点数和总边数:" << "\t";
	cin >> vexnum >> arcnum;  //输入总顶点数和总边数;
	//1. 完成对所有顶点的信息的输入。
	for (int i = 0; i < vexnum; i++)
	{
		cout << "请输入第" << i + 1 << "个顶点:" << "\t";
		cin >> vexs[i];
	}
	//2.对邻接矩阵进行初始化工作；将各条边的权值置为最大值;
	//对角线上的元素置为 0， 其它边的元素置为最大，即Maxlnt
	for (int i = 0; i < vexnum; i++)
	{
		for (int j = 0; j < vexnum; j++)
		{
			if (i == j) arcs[i][j] = 0;
			else arcs[i][j] = Maxlnt;
		}
	}
	//3.完成对邻接矩阵中各条边的赋值;
	for (int k = 0; k < arcnum; k++)
	{
		char v1, v2;
		int w;
		cout << "请分别输入第" << k + 1 << "条边的两个顶点和权值:" << "\t";
		cin >> v1 >> v2 >> w;
		int i = Locate_vex(v1);
		int j = Locate_vex(v2);
		//将边(v1,v2)和其对称边(v2,v1)的权值都值为w;
		arcs[i][j] = arcs[j][i] = w;
	}
	return OK;
}

void AMGraph::print()
{
	cout << endl << "顶点表的信息: " << endl;
	for (int i = 0; i < vexnum; i++)
	{
		cout << vexs[i] << " ";
	}
	cout << endl;
	cout << "邻接矩阵的信息:" << endl;
	for (int i = 0; i < vexnum; i++)
	{
		for (int j = 0; j < vexnum; j++)
		{
			if (arcs[i][j] == Maxlnt)
				cout << "∞" << "\t";
			else cout << arcs[i][j] << "\t";
			if (j == vexnum - 1)
				cout << endl;
		}
	}

}

int minEdge(SE* array, int n)
{
	int min = Maxlnt;
	int mark;
	for (int i = 0; i < n; i++)
	{
		if (array[i].lowcost != 0 && array[i].lowcost < min)
		{
			min = array[i].lowcost;
			mark = i;
		}
	}
	return mark;
}

void output_SMT(int k, SE* array,char c)
{
	cout << "(" << array[k].adjvex;
	cout << " , " << c << ")" << "\t" << array[k].lowcost << endl;
}

void Prim(AMGraph G)
{
	int start, k;
	char c;
	SE* shortEdge;
	shortEdge = new SE[G.vexnum];

	//1. 对初始辅助数组进行赋初值;
	cout << "请输入最小生成树的起点: " << "\t";
	cin >> c;
	start = G.Locate_vex(c);                                  //输入起点在顶点表当中的序号
	for (int i = 0; i < G.vexnum; i++)
	{
		shortEdge[i].lowcost = G.arcs[start][i];
		shortEdge[i].adjvex = G.vexs[start];
	}

	shortEdge[start].lowcost = 0;                             //将起点加入算法思想当中的U集合当中。
	for (int i = 0; i < G.vexnum - 1; i++)
	{
		k = minEdge(shortEdge, G.vexnum);                    //寻找最短边的邻接点的序号;
		output_SMT(k,shortEdge,G.vexs[k]);                   //输出最小生成树的路径;
		shortEdge[k].lowcost = 0;                            //将该顶点加入到算法思想当中的U集合当中;
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[k][j] < shortEdge[j].lowcost)
			{
				shortEdge[j].lowcost = G.arcs[k][j];
				shortEdge[j].adjvex = G.vexs[k];
			}
		}
	}
	delete[]shortEdge;
}


int main()
{
	int minEdge(SE * array, int n);
	void output_SMT(int k, SE * array);
	AMGraph p1;
	p1.creat_graph();
	p1.print();
	cout << endl;
	cout << "最小生成树路径为:" << endl;
	Prim(p1);
	return 0;
}

一、测试数据:

二、测试结果:

谢谢你的收看！

这篇关于普里姆算法求图(邻接矩阵存储)的最小生成树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！