Prim 算法、Kruskal 算法和去边法求无向图的最小代价生成树

///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（