///Coded?by?LC?2014/12/26///
#include“iostream“
#include“cstdlib“
#include“limits.h“
#include“string“
#define?INFINITY?INT_MAX
#define?MAX_VERTEX_NUM?20???
using?namespace?std;
int?Vexnum;???
typedef?struct{???
???int?vexnum;
???long?arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
}MGraph;
////////////////////////////////////////////////
void?CreateMGraph（MGraph*）;
void?Create（MGraph*）;
void?MiniSpanTree_PRIM（MGraph*MGraph*int）;
void?Print（MGraph*）;
void?MiniSpanTree_KRUSKAL（MGraph*MGraph*）;
void?Copy（MGraph*MGraph*）;
void?PathJudge（MGraph*intintint*int?[]）;
void?MiniSpanTree_CircleDestroy（MGraph*MGraph*）;
int?Find（int*int?[]int?[]MGraph*）;
void?findMax（int?[]intintint*int*MGraph*）;
////////////////////////////////////////////////?
int?main（）???
{???
????cout<<“Please?input?the?number?of?the?vertices:“;???
????cin>>Vexnum;
????MGraph?GG1G2G3;???
????CreateMGraph（&G）;???
????CreateMGraph（&G1）;???
????CreateMGraph（&G2）;???
????CreateMGraph（&G3）;
????Create（&G）;
????cout<<“PRIM“<	MiniSpanTree_PRIM（&G&G10）;?Print（&G1）;
	cout<<“KRUSKAl“<	MiniSpanTree_KRUSKAL（&G&G2）;?Print（&G2）;
	cout<<“CircleDestroy“<	MiniSpanTree_CircleDestroy（&G&G3）;?Print（&G3）;
????system（“pause“）;???
????return?0;???
}???
////////////////////////////////////////////////
void?CreateMGraph（MGraph*?G）?
{???
????（*G）.vexnum=Vexnum;???
????for（int?i=0;i???????for（int?j=0;j??????????（*G）.arcs[i][j]=INFINITY;???
}???
void?Create（MGraph*?G）??
{???
????cout<<“Please?input?the?matrix（use?-1?to?represent?INFINITY）“<????int?m;???
????for（int?i=0;i???????for（int?j=0;j??????????cin>>m;???
??????????if（m>0）???
?????????????（*G）.arcs[i][j]=m;???
??????????else???
?????????????（*G）.arcs[i][j]=INFINITY;???
???????}???
}???
////////////////////////////////////////////////??
void?MiniSpanTree_PRIM（MGraph*?GMGraph*?G1int?u）
{???
????struct
	{????
???????int?adjvex;???
???????int?lowcost;
????}closedge[Vexnum];???
????int?k;???
????for（int?i=0;i???????if（i!=u）
	???{???
??????????closedge[i].adjvex=u;???
??????????closedge[i].lowcost=（*G）.arcs[u][i];???
???????}???
????closedge[u].lowcost=0;
????for（int?i=1;i	{
???????long?min=INFINITY;???
???????for（int?m=0;m	???{
??????????if（closedge[m].lowcost>0&&closedge[m].lowcost		??{???
?????????????min=closedge[m].lowcost;???
?????????????k=m;???
??????????}
	???}
???????（*G1）.arcs[closedge[k].adjvex][k]=（*G1）.arcs[k][closedge[k].adjvex]=（*G）.arcs[k][closedge[k].adjvex];???
???????closedge[k].lowcost=0;
???????for（int?j=0;j	???{????
??????????if（（*G）.arcs[k][j]		??{???
?????????????closedge[j].adjvex=k;???
?????????????closedge[j].lowcost=（*G）.arcs[k][j];???
??????????}
	???}
????}???
}???
???
void?Print（MGraph*?G）
{???
????cout<<“The?minispantree:“<????for（