#include"stdio.h"
#include"graphics.h"
#define INFINITY 32767
#define MAX_VERTEX_NUM 20  /*最大頂點數*/

typedef struct ArcCell
{  /*定義鄰接矩陣*/
    int adj;
    char *info;
}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  

typedef struct VertexCell
{   
    /*定義頂點結構*/
    char v;     /*頂點值*/
    int x,y;    /*頂點在屏幕中的坐標*/
    int flag;   /*標識該頂點是否已在生成樹中*/
}Vertex;    

typedef struct MatrixGraph
{  
    /*定義圖結構*/
    Vertex vex[MAX_VERTEX_NUM];  /*圖的頂點結構數組*/
    AdjMatrix arcs;                   /*圖的鄰接矩陣*/
    int vexnum,arcnum;                /*圖的實際頂點數和弧數*/   
}MGraph;

struct
{     
    /*定義當前尚未包含到最小生成樹中的頂點的輔助結構*/        
    int lowcost;   /*該頂點當前到達最小生成樹的最小代價*/
    int adj;       /*該頂點當前通過與最小生成樹中的頂點adj相連而具有最小代價*/
}NoInTreeVex[MAX_VERTEX_NUM];

typedef struct
{   
    /*定義最小生成樹中的弧結構，用于存放最小生成樹的弧*/
    char v1,v2;    /*弧兩端的頂點*/ 
    int cost;      /*弧的代價*/
}PrimTreeArc;

struct 
{   
    /*定義最小生成樹結構，用于存放最后生成的最小生成樹*/
    PrimTreeArc arc[MAX_VERTEX_NUM];  /*最小生成數的弧*/
    char v[MAX_VERTEX_NUM];           /*最小生成樹的頂點*/
}PrimTree;

/*創建指定圖*/
void CreateAppMGraph(MGraph *G)
{
    int i,j;
    int VerXY[][2]={{300,100},{230,150},{300,200},{370,150},{240,250},{360,250}}; 
    /*VerXY[][2]存放事先指定的圖的各頂點的坐標*/
    G->vexnum=6;   /*指定圖的頂點數*/ 
    G->arcnum=10;  /*指定圖的弧數*/
    for(i=0;i<G->vexnum;i++)
	{
        G->vex[i].v='A'+i;  /*初始化各頂點的值，依次為A至F*/
        G->vex[i].flag=0;   /*各頂點初始時均未包含在最小生成樹中*/
	}
    /*以下為創建指定圖的鄰接矩陣*/
    for(i=0;i<G->arcnum;i++)
      for(j=0;j<G->vexnum;j++)
	    G->arcs[i][j].adj=INFINITY;  
    for(i=0;i<G->vexnum;i++)
    {
		G->vex[i].x=VerXY[i][0];
        G->vex[i].y=VerXY[i][1];
	}
    G->arcs[0][1].adj=G->arcs[1][0].adj=6;
    G->arcs[0][2].adj=G->arcs[2][0].adj=1;
    G->arcs[0][3].adj=G->arcs[3][0].adj=5;
    G->arcs[1][2].adj=G->arcs[2][1].adj=5;
    G->arcs[1][4].adj=G->arcs[4][1].adj=3;
    G->arcs[2][3].adj=G->arcs[3][2].adj=5;
    G->arcs[2][4].adj=G->arcs[4][2].adj=6;
    G->arcs[2][5].adj=G->arcs[5][2].adj=4;
    G->arcs[3][5].adj=G->arcs[5][3].adj=2;
    G->arcs[4][5].adj=G->arcs[5][4].adj=6;
}

/*返回頂點v在圖中的位置，也就是在頂點數組中的下標*/
int FindVex(MGraph *G,char v)  
{
    int i;
    for(i=0;i<G->vexnum;i++)
        if(G->vex[i].v==v)
	return i;
}

/*畫頂點*/
void DrawVex(Vertex vex)
{
    int VexR=15;
    char str[2];
    setfillstyle(1,RED);
    fillellipse(vex.x,vex.y,VexR,VexR);
    sprintf(str,"%c",vex.v);
    moveto(vex.x-2,vex.y-2);
    settextstyle(0,0,0);
    outtext(str);
}

/*畫弧*/
void DrawArc(Vertex vex1,Vertex vex2,int cost)
{
    char str[2];
    setcolor(WHITE);
    line(vex1.x,vex1.y,vex2.x,vex2.y);
    sprintf(str,"%d",cost);
    settextstyle(0,0,2);
    outtextxy((vex1.x+vex2.x)/2,(vex1.y+vex2.y)/2,str);
}

/*顯示整個圖*/
void ShowGraph(MGraph *G)
{
    int i,j,x,y;
    int VexR=15;
    char *str;
    setcolor(WHITE);
    for(i=0;i<G->vexnum;i++)
      for(j=i+1;j<G->vexnum;j++)
      {
	      if(G->arcs[i][j].adj!=INFINITY) /*只當相鄰時才畫弧，INFINITY表示不相鄰*/
	          DrawArc(G->vex[i],G->vex[j],G->arcs[i][j].adj);
      }
    for(i=0;i<G->vexnum;i++)
        DrawVex(G->vex[i]);
}

/*找到當前具有最小代價的尚未包含在最小生成樹中的頂點*/
int FindLowcostVex(MGraph *G)
{
    int i,j,min;
    min=INFINITY;
    for(i=0;i<G->vexnum;i++)
	{
        if(!G->vex[i].flag && NoInTreeVex[i].lowcost<min)
		{  /*如果頂點i尚未包含在最小生成樹中，且其當前到達最小生成樹的代價小于最小代價*/
	        min=NoInTreeVex[i].lowcost;  /*則取頂點i的代價為最小代價*/
	        j=i;   /*保留頂點i的位置i*/
		}
	}
    return j;   /*返回具有到達最小生成樹的最小代價的頂點位置*/
}

/*執行普里姆算法，求得最小生成樹*/
void Prim(MGraph *G,char v)  
{
    /*參數v為求最小生成樹的開始頂點*/
    int i,j,k;
    int min;

    k=FindVex(G,v);  /*找到開始頂點在圖中的位置（即頂點數組下標）*/
    PrimTree.v[0]=v;  /*首先將開始頂點置于最小生成樹的頂點集合中*/
    /*此時最小生成樹只包含開始頂點*/
    G->vex[k].flag=1; /*標識開始頂點已在最小生成樹中*/
    for(i=0;i<G->vexnum;i++) 
	{
     /*對輔助結構數組NoInTreeVex[]進行初始化*/
        if(i==k)  
	        NoInTreeVex[i].lowcost=0;
/*如果為開始頂點，則開始頂點到達最小生成樹的代價為0，表示已在最小生成樹中*/
        else  
		{
	        NoInTreeVex[i].lowcost=G->arcs[i][k].adj;
/*否則，頂點i到達最小生成樹的代價初始為頂點i到達開始頂點的代價*/
	      NoInTreeVex[i].adj=k; /*頂點i通過開始頂點（k）與最小生成樹相連*/ 
		}
        DrawVex(G->vex[i]);  /*畫每個頂點*/
	}
    getch();
  
    for(i=1;i<G->vexnum;i++)
	{
/*從除去開始頂點的下一個頂點開始，依次將每個頂點包含到最小生成樹中來*/
       k=FindLowcostVex(G);
/*找到當前具有到達最小生成樹最小代價的頂點，用k表示*/  
       j=NoInTreeVex[k].adj;  /*求得這個頂點與最小生成樹相連的頂點，用j表示*/
       DrawArc(G->vex[k],G->vex[j],G->arcs[k][j].adj);
/*先畫出具有最小代價的頂點k與最小生成樹相連的弧*/
       DrawVex(G->vex[k]);  /*然后畫頂點k和與之相連的頂點j*/
       DrawVex(G->vex[j]);
       PrimTree.v[i]=G->vex[k].v; /*將頂點k保存到最小生成樹的頂點數組中*/
       PrimTree.arc[i].v1=G->vex[j].v;
/*將頂點k到達最小生成樹的弧保存，包括兩端頂點與代價*/
       PrimTree.arc[i].v2=G->vex[k].v;
       PrimTree.arc[i].cost=G->arcs[j][k].adj;
       G->vex[k].flag=1;   /*表示頂點k已包含在最小生成樹中*/
       /*此時生成了新的當前最小生成樹，即有新的頂點k包含進來*/
       getch();
/*以下是根據新的當前最小生成樹來調整尚未包含到生成樹中的頂點到達生成樹的代價*/
       for(j=0;j<G->vexnum;j++)
	   {
	       if(G->vex[j].flag==0)  /*如果該頂點尚未包含在生成樹中，則*/
	         if(G->arcs[k][j].adj<NoInTreeVex[j].lowcost)
			 {/*如果該頂點到達新包含進來的頂點k的代價小于之前到達生成樹的代價*/
                 NoInTreeVex[j].lowcost=G->arcs[k][j].adj;
                 /*則該頂點到達生成樹的代價變為該頂點到達頂點k的代價*/
		         NoInTreeVex[j].adj=k; /*且該頂點與生成樹相連的頂點變為頂點k*/ 
			 }
	   }
	}
}

main()
{
    MGraph G;
    int gd=DETECT,gm;
    initgraph(&gd,&gm,"c:\\tc");
    setbkcolor(BLACK);
    CreateAppMGraph(&G);
    ShowGraph(&G);
    getch();
    clearviewport();
    setbkcolor(BLACK);
    Prim(&G,'A');
}