最小生成树 ----prim 算法 ----prim 算法

#include<iostream>
using namespace std;
#define MAX 10//图中最大的顶点数
#define INFINITY 65535//表示趋向无穷大
typedef char DataType;
//定义shortEdge结构体
struct shortEdge 
{
	int lowcost;//最低代价
	int adjvex;//起点
};
//有向网图的邻接矩阵
class Graph 
{
private:
	int vertex[MAX];//存放顶点信息的数组
	int arc[MAX][MAX];//存放边信息的数组
	int verNum;//顶点数
	int arcNum;//边的个数
	int visit[MAX];//访问数组
	shortEdge* se;//shortEdge结构体数组指针
public:
	//第一个参数：用户传入的顶点数组 第二个参数：顶点个数 第三个参数：边的个数
	Graph(DataType ver[],int n,int e);
	//DFS--深度优先递归---v表示从某一个顶点开始进行遍历
	void DFS(int v);
	//深度优先遍历
	void DFSTravers();
	//输出邻接矩阵
	void output()
	{
		for (int i = 0; i < verNum; i++)
		{
			for (int j = 0; j < verNum; j++)
			{
				cout << arc[i][j] << " \t";
			}
			cout << endl;
		}
	}
	//prim算法----start表示以某个顶点为起点来生成最小树
	void Prim(int start);
	//minEdge函数
	int minEdge( int start);
};
Graph::Graph(DataType ver[],int n,int e)
{
	//顶点个数初始化
	verNum = n;
	//边数初始化
	arcNum = e;
	//初始化顶点数组
	for (int i = 0; i < verNum; i++)
	{
		vertex[i] = ver[i];
	}
	//初始化边数组
	for (int i = 0; i < arcNum; i++)
	{
		for (int j = 0; j < arcNum; j++)
		{
			if (i == j)
			{
				arc[i][j] = 0;
			}
			else 
			{
				arc[i][j] = INFINITY;
			}
		}
	}
	//用户输入边的关系
	int vi = 0., vj = 0,w=0;
	for (int i = 0; i < arcNum; i++)
	{
		cout << "请输入边依附的两个顶点编号（范围0-5）和权值:  ";
		cin >> vi >> vj >> w;
		//因为是无向图，所以矩阵对称
		arc[vi][vj] = w;
		arc[vj][vi] = w;
		cout << endl;
	}
	//初始化访问数组
	for (int i = 0; i < verNum; i++)
		visit[i] = 0;//0表示没有被访问过
}
//深度优先递归
void Graph::DFS(int v)
{
	//设置访问标志
	visit[v] = 1;
	//输出该顶点信息
	cout << vertex[v]<<" ";
	//访问该顶点的邻接点
	for (int i = 0; i < verNum; i++)
	{
		//两顶点间有边----邻接点
		//判断该顶点有没有被访问过
		if (arc[v][i] == 1&& visit[i] == 0)//没被访问过，就访问该顶点，然后再去访问该顶点的邻接点
		{
				DFS(i);
	     }
	}
}
//深度优先遍历
void Graph::DFSTravers()
{ 
	//遍历所有节点，防止出现某个节点没有被访问过的情况
	for (int i = 0; i < verNum; i++)
	{
		DFS(i);
	}
}
//输出最小生成树的路径
void outputMST(shortEdge* se,int k)
{
	cout << "(" << se[k].adjvex << "," << k << ")" << se[k].lowcost << endl;
}
//Prim算法
void Graph::Prim(int start)
{
	se = new shortEdge[verNum];//在堆区创建最短边结构体数组
	if (se == NULL)
		return;
	//初始化结构体数组
	for (int j = 0; j < verNum; j++)
	{
		se[j].lowcost = arc[start][j];//将start顶点所在arc边数组的那一行v0到其他顶点的权值信息存入lowcost中，进行初始化操作
		se[j].adjvex = start;//初始化都为start顶点的下标
	}
	//起点start放入集合U
	se[start].lowcost= 0; //lowcost=0表示放入集合U
	//注意循环结束条件是verNum-1,因为最小生成树只有N-1条边
	for (int i = 0; i < verNum-1; i++)
	{
		//寻找从当前顶点出发到达所有与之有边的顶点，找到耗费最小代价就可以到达的邻接点k
		int k = minEdge(start);
		outputMST(se,k);//输出最小生成树的路径
		//将当前顶点K加入集合U中
		se[k].lowcost = 0;
		//调整结构体数组里面的值
		//遍历当前结构体数组，如果新加入的顶点K到他的邻接点的代价小于当前lowcost数组中记录的代价，就进行替换
		for (int i = 0; i < verNum; i++)
		{
			//当前K顶点在边数组里面与每个顶点之间的权值与结构体数组 在 当前U集合中D的顶点到每一个顶点之间最小代价进行对比
			if (arc[k][i] < se[i].lowcost)
			{
				se[i].adjvex = k;//替换当前起点
				se[i].lowcost = arc[k][i];//替换最小代价
			}
		}
	}
}
//寻找耗费代价最小的邻接点
int Graph::minEdge(int start)
{
	int min = INFINITY;//初始化最小的权值为无穷大
	int k = 0;//假设下标为k的元素权值最小
	int j = 0;
	//通过这个while循环找出当前结构体数组中最小的lowcost值的在结构体数组中的下标，也代表着第几个顶点
	while (j < verNum)
	{
		//如果当前lowcost不等于0,表示当前顶点没有被放入集合U
		if (se[j].lowcost != 0 && se[j].lowcost < min)
		{
			min = se[j].lowcost;//让当前权值成为最小值
			k = j;//将当前的最小值的下标存入K
		}
		j++;
	}
	return k;
}
//
//测试----------
void test()
{
	//顶点信息数组
	DataType v[6] = { 0,1,2,3,4,5 };
	//边的个数
	int e = 9;
	//顶点个数
	int n = 6;
	//构造函数
	Graph p(v, n, e);
	//深度优先遍历
	cout << "输出边数组信息：" << endl;;
	p.DFSTravers();
	cout << endl;
	cout << "输出邻接矩阵信息： " << endl;
	p.output();
	cout << "从起点开始最小生成树：" << endl;
	p.Prim(3);
}
int main()
{

	test();
	system("pause");
	return 0;
}