长假最后一天，前六天时间基本上什么都没做，今天起了个大早决定在自习室度过，把“未竟的事业”完成，哈哈。。。数据结构进展奇慢，算法真的好难学，理解一个算法的实现过程还比较容易，真正把它写成代码可没那么容易了。这个算法竟然从早上8点写到现在才实现，解决了一些难以发现的小细节。感觉不错，加油努力！

昨天看到了乔布斯去世的消息，有点意外，有点难过，一代天才就这样陨落了。乔布斯是我的偶像来着，我的桌面背景，甚至输入法的皮肤都是乔布斯，我喜欢苹果，喜欢乔布斯，虽然到现在为止我都没有拥有过一部苹果的产品。乔布斯不只是一个天才，他代表了一个时代，它是一种符号，或者说一种精神的象征。在苹果，他不只是CEO，还是苹果的精神领袖。不知道失去了乔布斯的苹果还能否延续辉煌。

head.h

#include<iostream>
using namespace std;

#define MAX_VEX_NUM 20
#define STATE int//标示是否被选入了集合
#define IN 1
#define OUT 0

class VexBox //顶点类
{
public:
	VexBox();
	char vexname; //顶点名称
	int lowcost; //记录依附于该顶点的所有边中最短边的边长
	int adjvex; //记录与该顶点共同构成上述那条边的另一个顶点
	STATE state; //记录该顶点是否已被选入集合中
};

VexBox::VexBox()
{
	state = OUT;
}

class MSTMap //最小生成树的存储结构类
{
public:
	MSTMap();
	int vexnum; //顶点总数
	int cost[MAX_VEX_NUM][MAX_VEX_NUM]; //用二维数组记录每条边的权值
	VexBox vexbox[MAX_VEX_NUM]; //顶点集
};

MSTMap::MSTMap()
{
	vexnum = 0; //初始化顶点数
	for (int i = 0; i < MAX_VEX_NUM; i++) //初始化权值
	{
		for (int j = 0; j < MAX_VEX_NUM; j++)
		{
			cost[i][j] = INT_MAX;
		}
	}
}

class Prime //实现Prime算法的类
{
public:
	void GetMSTree(); //接口函数
private:
	void GetVex(); //得到顶点信息
	void GetEdge(); //得到边的信息
	void GetClosedge(); //得到依附于每个顶点的最短边
	void Spaning(); //处理过程
	MSTMap m;
};

void Prime::GetMSTree() //接口函数
{
	GetVex();
	GetEdge();
	Spaning();
}
;

void Prime::GetVex() //得到顶点信息
{
	cout << "Please Enter The Name Of Each Vertex  :" << endl << endl;
	char name;
	while (cin >> name)
	{
		m.vexbox[m.vexnum++].vexname = name;
	}
	cin.clear();
}

void Prime::GetEdge() //得到边的信息
{
	cout << "Please Enter The Edges Follow The Formate As Been Shown Below:"
			<< endl << "vexnum1  vexnum2  weight" << endl << endl;
	int vexnum1, vexnum2, weight;
	while (cin >> vexnum1 >> vexnum2 >> weight)
	{
		m.cost[vexnum1][vexnum2] = m.cost[vexnum2][vexnum1] = weight;
	}
	cin.clear();
}

void Prime::GetClosedge() //得到依附于每个顶点的最短边
{
	int min, vexpos;
	for (int i = 0; i < m.vexnum; i++)
	{
		min = INT_MAX;
		vexpos = -1;
		for (int j = 0; j < m.vexnum; j++)
		{
			if (m.vexbox[i].state == IN && m.vexbox[j].state == IN) //消去两个顶点都在集合中的边
			//这个步骤很重要少了这一步的话在某些情况下会出错
			{
				m.cost[i][j] = m.cost[j][i] = INT_MAX;
			}
			if (m.cost[i][j] < min)
			{
				min = m.cost[i][j];
				vexpos = j;
			}
		}
		m.vexbox[i].adjvex = vexpos;				//记录位置信息
		m.vexbox[i].lowcost = min;				//记录最短边的长度
	}
}

void Prime::Spaning()				//处理过程
{
	GetClosedge();				//初始化
	int recycle = m.vexnum - 2;
	int min, vexpos;
	//处理前两个顶点
	int weight = m.vexbox[0].lowcost;
	cout << m.vexbox[0].vexname << "--" << weight << "--"
			<< m.vexbox[m.vexbox[0].adjvex].vexname << endl;
	m.vexbox[0].state = m.vexbox[m.vexbox[0].adjvex].state = IN;
	m.cost[0][m.vexbox[0].adjvex] = m.cost[m.vexbox[0].adjvex][0] = INT_MAX;
	//处理剩余的顶点
	while (recycle--)
	{
		GetClosedge();
		min = INT_MAX;
		vexpos = 0;
		for (int i = 0; i < m.vexnum; i++)
		{
			if (m.vexbox[i].state == IN
					&& m.vexbox[m.vexbox[i].adjvex].state == OUT
					&& m.vexbox[i].lowcost < min)
			{
				min = m.vexbox[i].lowcost;
				vexpos = i;
			}
		}
		cout << m.vexbox[vexpos].vexname << "--" << min << "--"
				<< m.vexbox[m.vexbox[vexpos].adjvex].vexname << endl;
		weight += min;
		m.vexbox[m.vexbox[vexpos].adjvex].state = IN;
		m.cost[vexpos][m.vexbox[vexpos].adjvex] =
				m.cost[m.vexbox[vexpos].adjvex][vexpos] = INT_MAX;
	}
	cout << "Weight = " << weight << endl;				//输出总权值和
}

main.cpp

#include"head.h"

int main()
{
	Prime p;
	p.GetMSTree();
	system("pause");
}