minispantree.cpp

文件夹中包括常用的数据结构的算法

#include <stdio.h>

#define MAX_VERTEX_NUM	20
#define  V_NUM  6
#define MAX_EDGE 1000
#define  SELECTED  0
#define Maxsize 100


typedef struct MGraph
{
	char  vexs[V_NUM] ;// 顶点向量
	int	 arcs[V_NUM][V_NUM];			// 邻接矩阵
	int	 vexnum , arcnum;		// 顶点数和弧数
//	GraphKind 	kind;				// 图的类型
}MGraph;


struct closedge
{    char  adjvex;  // U集中的顶点序号
     int  lowcost;  // 边的权值
}closedge[MAX_VERTEX_NUM];



void MiniSpanTree_Prim(MGraph &G, char u)  //用普里姆算法从顶点u出发构造网G的最小生成树
{
	  int miniedge = MAX_EDGE; //求出加入生成树的下一个顶点(k)时用于放最小边
	  int k = u - G.vexs[0];       //k = LocateVex ( G, u ); 

      for (int j=0; j<G.vexnum; ++j )  // 辅助数组初始化
      {
		  if (j!=k)  
          closedge[j].adjvex = u;                   //= { u, G.arcs[k][j].adj };  
          closedge[j].lowcost = G.arcs[k][j];       // 邻接矩阵用权值表示
	  }
      closedge[k].lowcost = SELECTED;      // 初始，U＝{u} u被选中
      
	  for (int i=1; i<G.vexnum; ++i)   //循环n-1次，找到n-1条边
	  {
		  miniedge = MAX_EDGE;
	      for (int a=0; a<G.vexnum; ++a)        // k = minimum(closedge);    // 求出加入生成树的下一个顶点(k)
		  {
			  if(closedge[a].lowcost != SELECTED && (closedge[a].lowcost < miniedge))
			  {
			      miniedge = closedge[a].lowcost;
				  k = a;
			  }
		  };
                 
          printf("%c,  %d, %c\n", closedge[k].adjvex, closedge[k].lowcost, G.vexs[k]); // 输出生成树上一条边
                    
          closedge[k].lowcost = SELECTED;    // 第k顶点并入U集

          for (j=0; j<G.vexnum; ++j)  //修改其它顶点的最小边
		  {        
              if (closedge[j].lowcost != SELECTED && G.arcs[k][j] < closedge[j].lowcost)
			  {
			      closedge[j].adjvex = G.vexs[k];   //{ G.vexs[k], G.arcs[k][j].adj};
                  closedge[j].lowcost = G.arcs[k][j];
			  };
		  };
	  }
}



struct edges          //克鲁斯卡尔算法中要用到的边的集合 
{
	char bv,tv;
	int w;
};

int seeks(int set[], char v)      //查找顶点v对应的连通集
{                                 //对于个顶点分别返回其所对应连通分量号，若set[i]〉0说明曾经选中过
	char i=v-'a';                 //那么要利用循环"统一"在一个连通分量中的顶点对应的集合号
	while(set[i]>0)               //在跳出循环后保证在一个连通分量中的顶点对应的集合号相同，
		i=set[i];
	return i;
}

void MinSpanTree_Kruscal()
{
    edges ge[Maxsize];
	int vertexNum, edgeNum;
	int v1,v2,i,j;
	int set[Maxsize];

///////////////////////////////////////////////////////////////////////////////
	printf("请输入边数：\n");                             //构造图（用结构edges表示）
	scanf("%d",&edgeNum);
	printf("请输入顶点数：\n");
	scanf("%d",&vertexNum);
	printf("请按顺序输入每条边的两个顶点及其权值：\n");
	getc(stdin);  //因为下面要用标准输入流作处理，先读取流的首字符不做处理
	for(int a=1;a <= edgeNum; a++)  //scanf("%c,%c,%d",&ge[i].bv,&ge[i].tv,&ge[i].w);   //构造图（用结构edges表示）
	{
	   ge[a].bv = getc(stdin);   ////从标准输入流中读取
	   ge[a].tv = getc(stdin);
       ge[a].w  = (int)(getc(stdin)-48);
	}
		
///////////////////////////////////////////////////////////////////////////////

	for(i=1; i <= vertexNum; i++) set[i]=0;    //初始化连通

	i=1;
	j=1;
	while(j<=vertexNum && i<= edgeNum)     //i用来控制在边的集合ge[Maxsize]中依次找边，j用来控制最小生成树中共有e条边
	{
		v1=seeks(set, ge[i].bv);    //对于两个顶点分别返回其所对应连通分量号
		v2=seeks(set, ge[i].tv);
		if(v1!=v2)
		{
			printf("(%c,  %c)",ge[i].bv,ge[i].tv);
			set[v1]=v2;
			j++;
		}
		i++;

	}
	printf("\n");

}


void main()
{
	/////////////////////////////////////////////////////////////////////////////////////
	/*Prim算法*/
    MGraph G;
    int arcsMatrix[V_NUM][V_NUM] = {0, 6, 1, 5, 0, 0, 
		                            6, 0, 5, 0, 3, 0,
									1, 5, 0, 5, 6, 4,
									5, 0, 5, 0, 0, 2,
									0, 3, 6, 0, 0, 6, 
									0, 0, 4, 2, 0, 0,};
	G.vexnum = V_NUM;
	for(int i = 0; i < V_NUM; i++)
	{
		G.vexs[i] = 'A'+i;      //// 顶点向量
	    for(int j = 0; j < V_NUM; j++)
		{
			if(arcsMatrix[i][j] == 0)
			{
			    G.arcs[i][j] = MAX_EDGE ;
			}
			else{G.arcs[i][j] = arcsMatrix[i][j];};
		}
	}; 

    MiniSpanTree_Prim(G, 'A');


/////////////////////////////////////////////////////////////////////////////////////////
	/*克鲁斯卡尔算法算法演示*/
	MinSpanTree_Kruscal();
}