4-8.c

< c程序员成长攻略>>源代码,一本很好的书,原书全部的代码都有讲解,是c程序员的福星

#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');
}