最小生成树：Prim算法

最小生成树

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

Prim算法

Prim算法是解决最小生成树的常用算法。它采取贪心策略，从指定的顶点开始寻找最小权值的邻接点。图G= ，初始时S={V0}，把与V0相邻接，且边的权值最小的顶点加入到S。不断地把S中的顶点与V-S中顶点的最小权值边加入，直到所有顶点都已加入到S中。

实例

从V0开始

?

代码

类定义

?

#include
  
     
#include
   
     #include
    
      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[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;
}
//更新最近边
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 << ******Floyd***by David*** << endl;
	int numV, numE;
	cout << 建图... << endl;
	cout << 输入顶点数 ;
	cin >> numV;
	Graph graph(numV);
	cout << 输入边数 ;
	cin >> numE;
	graph.createGraph(numE);
	cout << endl << Prim... << endl;
	for (int i = 0; i < numV/2; i++)
		graph.Prim(i);
	system(pause);
	return 0;
}

?

?

?

?

?