数据结构：最小生成树--Prim算法

时间：2023-03-09 17:59:01
数据结构：最小生成树--Prim算法

最小生成树：Prim算法

最小生成树

给定一无向带权图。顶点数是n，要使图连通仅仅需n-1条边。若这n-1条边的权值和最小，则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost spanning tree)。

Prim算法

Prim算法是解决最小生成树的经常使用算法。

它採取贪心策略，从指定的顶点開始寻找最小权值的邻接点。图G=<V,E>。初始时S={V0}。把与V0相邻接。且边的权值最小的顶点增加到S。

不断地把S中的顶点与V-S中顶点的最小权值边增加，直到全部顶点都已增加到S中。

算法说明

为了方便寻找最小权值的边，构建一近期边结构体CloseEdge：

//近期边

typedef struct closeedge_tag

{

	int adjvex; //邻接点

	int weight; //权值

}CloseEdge;

创建一数组CloseEdge closeedge[n];顶点u属于S，顶点v属于V-S，则closeedge[v].weight=min{weight(u,v)};closeedge[v].adjvex=u;另外设置一bool型的数组add，标记顶点i是否已增加S。结合closeedge和add就可以得到当前最小权值边。

每当有新的节点增加S时。则需更新closeedge。

详细细节看代码。

实例

数据结构：最小生成树--Prim算法

从V0開始

数据结构：最小生成树--Prim算法

代码

类定义

#include<iostream>

#include<iomanip>

#include<stack>

using namespace std;

#define MAXWEIGHT 100

//边

typedef struct edge_tag

{

	int tail;

	int head;

}Edge;

//近期边

typedef struct closeedge_tag

{

	int adjvex; //邻接点

	int weight; //权值

}CloseEdge;

class Graph

{

private:

	//顶点数

	int numV;

	//边数

	int numE;

	//邻接矩阵

	int **matrix;

public:

	Graph(int numV);

	//建图

	void createGraph(int numE);

	//析构方法

	~Graph();

	//Prim算法

	void Prim(int);

	int minEdgeVex(CloseEdge*, bool*);

	void updateCloseEdge(CloseEdge*, bool*, int);

	//打印邻接矩阵

	void printAdjacentMatrix();

	//检查输入

	bool check(int, int, int);

};

类实现

//构造函数，指定顶点数目

Graph::Graph(int numV)

{

	//对输入的顶点数进行检測

	while (numV <= 0)

	{

		cout << "顶点数有误！

又一次输入 ";

		cin >> numV;

	}

	this->numV = numV;

	//构建邻接矩阵，并初始化

	matrix = new int*[numV];

	int i, j;

	for (i = 0; i < numV; i++)

		matrix[i] = new int[numV];

	for (i = 0; i < numV; i++)

	for (j = 0; j < numV; j++)

	{

		if (i == j)

			matrix[i][i] = 0;

		else

			matrix[i][j] = MAXWEIGHT;

	}

}

void Graph::createGraph(int numE)

{

	/*

	对输入的边数做检測

	一个numV个顶点的有向图，最多有numV*(numV - 1)条边

	*/

	while (numE < 0 || numE > numV*(numV - 1))

	{

		cout << "边数有问题。又一次输入 ";

		cin >> numE;

	}

	this->numE = numE;

	int tail, head, weight, i;

	i = 0;

	cout << "输入每条边的起点(弧尾)、终点(弧头)和权值" << endl;

	while (i < numE)

	{

		cin >> tail >> head >> weight;

		while (!check(tail, head, weight))

		{

			cout << "输入的边不对！

请又一次输入 " << endl;

			cin >> tail >> head >> weight;

		}

		//Prim算法主要针对的是无向图

		matrix[tail][head] = weight;

		matrix[head][tail] = weight;

		i++;

	}

}

Graph::~Graph()

{

	int i;

	for (i = 0; i < numV; i++)

		delete[] matrix[i];

	delete[]matrix;

}

/*

Prim算法

求最小生成树

*/

void Graph::Prim(int vertex)

{

	//有numV个顶点的图的最小生成树有numV-1条边

	Edge *edges = new Edge[numV - 1];

	//标记顶点是否增加

	bool *add = new bool[numV];

	memset(add, 0, numV);

	//先把vertex增加

	add[vertex] = true;

	//近期边

	CloseEdge *closeedge = new CloseEdge[numV];

	int i;

	//初始化近期边

	for (i = 0; i < numV; i++)

	{

		closeedge[i].weight = matrix[vertex][i];

		if (!add[i] && matrix[vertex][i] > 0 && matrix[vertex][i] < MAXWEIGHT)

			closeedge[i].adjvex = vertex;

	}

	int v, count = 0;

	while (count < numV - 1)

	{

		//获取近期边的邻接点

		v = minEdgeVex(closeedge, add);

		add[v] = true;

		//把最小权值边依次增加数组edges

		edges[count].tail = closeedge[v].adjvex;

		edges[count].head = v;

		//更新近期边

		updateCloseEdge(closeedge, add, v);

		count++;

	}

	cout << "从顶点 " << vertex << " 開始。最小生成树的边是" << endl;

	for (i = 0; i < count; i++)

		cout << edges[i].tail << "---" << edges[i].head << endl;

	//释放空间

	delete[]edges;

	delete[]add;

	delete[]closeedge;

}

//从closeedge中寻找最小边的邻接顶点

int Graph::minEdgeVex(CloseEdge *closeedge, bool *add)

{

	int i, v, w;

	v = 0;

	w = MAXWEIGHT;

	for (i = 0; i < numV ; i++)

	if (!add[i] && closeedge[i].weight < w)

	{

		w = closeedge[i].weight;

		v = i;

	}

	return v;

}

//顶点v的增加后，须要更新近期边

void Graph::updateCloseEdge(CloseEdge* closeedge, bool *add, int v)

{

	int i;

	for (i = 0; i < numV; i++)

	if (!add[i] && matrix[v][i] < closeedge[i].weight)

	{

		closeedge[i].adjvex = v;

		closeedge[i].weight = matrix[v][i];

	}

}

//打印邻接矩阵

void Graph::printAdjacentMatrix()

{

	int i, j;

	cout.setf(ios::left);

	cout << setw(7) << " ";

	for (i = 0; i < numV; i++)

		cout << setw(7) << i;

	cout << endl;

	for (i = 0; i < numV; i++)

	{

		cout << setw(7) << i;

		for (j = 0; j < numV; j++)

			cout << setw(7) << matrix[i][j];

		cout << endl;

	}

}

bool Graph::check(int tail, int head, int weight)

{

	if ((tail == head) || tail < 0 || tail >= numV

		|| head < 0 || head >= numV

		|| weight <= 0 || weight >= MAXWEIGHT)

		return false;

	return true;

}

主函数

int main()

{

	cout << "******Prim***by David***" << endl;

	int numV, numE;

	cout << "建图..." << endl;

	cout << "输入顶点数 ";

	cin >> numV;

	Graph graph(numV);

	cout << "输入边数 ";

	cin >> numE;

	graph.createGraph(numE);

	cout << endl << "Prim..." << endl;

	/*

	因为输出结果太长，不利于截图，故仅仅打印一半的节点

	要想获得从全部节点開始的最小生成树，改动i的变化范围就可以

	*/

	for (int i = 0; i < numV / 2; i++)

		graph.Prim(i);

	system("pause");

	return 0;

}

执行

数据结构：最小生成树--Prim算法数据结构：最小生成树--Prim算法

完整代码下载：Prim算法

转载请注明出处，本文地址：http://blog.csdn.net/zhangxiangdavaid/article/details/38377091

若有所帮助。顶一个哦。

专栏文件夹：

版权声明：本文博主原创文章，转载，转载请注明出处。

相关文章