第六章图-算法6.8普里姆算法

#pragma once
#include 

using namespace std;

//图的邻接矩阵存储(创建无向图)
//表示极大值
#define MaxInt 32767
//最大顶点数
#define MVNum 100
//顶点类型
typedef char VerTexType;
//边上的权值类型
typedef int ArcType;

typedef struct
{
	//顶点表
	VerTexType vexs[MVNum];
	//邻接矩阵
	ArcType arcs[MVNum][MVNum];
	//图中当前顶点数和边数
	int vexnum, arcnum;
}AMGraph;


//图G中查找顶点u，返回下标；不存在返回-1
int LocateVex(AMGraph G, VerTexType v)
{
	int i;
	for (i = 0; i < G.vexnum; i++)
	{
		if (v == G.vexs[i])
		{
			return i;
		}

	}
}

void CreateUDN(AMGraph& G)
{
	VerTexType v1, v2;
	ArcType w;
	int row;
	int col;
	//输入总顶点数，总边数
	cout << "请输总顶点数：";
	cin >> G.vexnum;
	cout << "请输总边数：";
	cin >> G.arcnum;
	//依次输入点的信息
	for (int i = 0; i < G.vexnum; i++)
	{
		cout << "输入顶点：";
		cin >> G.vexs[i];
	}
	//初始化邻接矩阵，边的权值置为最大值MaxInt
	for (int m = 0; m < G.vexnum; m++)
	{
		for (int n = 0; n < G.vexnum; n++)
		{
			G.arcs[m][n] = MaxInt;
		}
	}
	//构造邻接矩阵
	for (int k = 0; k < G.arcnum; k++)
	{
		cout << "输入边依附的顶点以及权值：";
		cin >> v1 >> v2 >> w;
		row = LocateVex(G, v1);
		col = LocateVex(G, v2);
		G.arcs[row][col] = w;
		G.arcs[col][row] = G.arcs[row][col];
	}
}

//输出无向网的邻接矩阵
void ShowGraph(AMGraph G)
{
	cout << "无向网的邻接矩阵为:" << endl;
	for (int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if (G.arcs[i][j]==MaxInt)
			{
				cout << "∞" << " ";
			}
			else
			{
				cout << G.arcs[i][j] << " ";
			}
			
		}
		cout << endl;
	}

}

//辅助数组的定义，用来记录顶点U到V-U的权值最小的边
struct
{
	VerTexType adjvex;//最小边在U中的那个顶点
	ArcType lowcost;//最小边上的权值
}closedge[MVNum];

//返回权值最小的点
int Min(AMGraph G)
{
	int minnum = INT_MAX;
	int index;
	for (int i = 0; i < G.vexnum; i++)
	{
		if (closedge[i].lowcost < minnum&&closedge[i].lowcost!=0)
		{
			minnum = closedge[i].lowcost;
			index = i;
		}
	}
	return index;
}

void MiniSpanTree_Prim(AMGraph G, VerTexType u)
{
	//K为顶点u的下标
	int k = LocateVex(G, u);
	//初始化
	for (int j = 0; j < G.vexnum; j++)
	{
		if (j != k)
		{
			closedge[j] = { u,G.arcs[k][j] };
		}
	}
	closedge[k].lowcost = 0;

	//选择其余n-1个顶点，生成n-1条边
	VerTexType u0, v0;
	for (int i = 1; i < G.vexnum; i++)
	{
		k = Min(G);
		//u0为最小边的一个顶点，u0∈U 
		u0 = closedge[k].adjvex; 
		//v0为最小边的另一个顶点，v0∈V-U 
		v0 = G.vexs[k];            			
		//输出当前的最小边(u0, v0) 				
		cout << "边  " << u0 << "--->" << v0 << endl;         
		//第k个顶点并入U集		
		closedge[k].lowcost = 0;   		 
		for (int j = 0; j < G.vexnum; j++)
			//新顶点并入U后重新选择最小边 
			if (G.arcs[k][j] < closedge[j].lowcost) 
			{						
				closedge[j].adjvex = G.vexs[k];
				closedge[j].lowcost = G.arcs[k][j];
			} 
	}
	
}

int main() {

	AMGraph G;
	//创建无向网的邻接矩阵
	CreateUDN(G);
	//输出无向网的邻接矩阵
	ShowGraph(G);

	cout << "******利用普里姆算法构造最小生成树结果：******" << endl;

	MiniSpanTree_Prim(G, '1');
	cout << endl;
	
	system("pause");
	return 0;
}