邻接矩阵和邻接链表的克鲁斯卡尔算法

#include   
#include   
#include
#define   MAX_NAME   5   /*顶点值最大字符数*/
#define   MAX_VERTEX_NUM   20     /*最大顶点数*/
typedef   char   Vertex[MAX_NAME];/*（邻接矩阵用）顶点名字串*/ 
typedef char VertexType[MAX_NAME];/*（邻接链表用）顶点名字串*/  
typedef   int   AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/   

/*链表的结点结构信息*/
typedef struct ArcNode{/*定义边结点*/
	int adjvex;   /*该弧指向的顶点的位置*/
	int weight;   /*该弧的权重*/
	struct ArcNode *nextarc;   /*指向下一条弧的指针*/
}ArcNode;

/*表头向量的结点结构信息*/
typedef struct VNode{ 
	VertexType data; /*顶点信息*/
	ArcNode *firstarc;  /*指向第一条依附该顶点的弧的指针*/
}VNodeAdjList[MAX_VERTEX_NUM];//定义图结点

/*链表带权图的结构信息*/
typedef struct{
	AdjList vertices;  /*表头向量*/
	int vexnumarcnum;//顶点数和弧数
}ALGraph;//定义图  

/*矩阵带权图的结构信息*/ 
struct   MGraph   
{   
    Vertex   vexs[MAX_VERTEX_NUM]; /*顶点向量*/    
    AdjMatrix   arcs;     /*邻接距阵*/
    int   vexnumarcnum;  /*顶点数和弧数*/
};     
int   LocateVex（MGraph   GVertex   u）//矩阵求点u所在位置   
{     
      int i;   
      for（i=0;i		  return   i;   
      return   -1;   
} 
int LocateVe（ALGraph GVertexType u）//链表求出点u所在位置   
{     
	int i;   
	for（i=0;i		if（strcmp（G.vertices[i].datau） == 0）
			return i;   
	return -1;   
} 

/*============================================*/
/*===========邻接链表的克鲁斯卡尔算法=========*/
/*============================================*/
void CreateGraph（ALGraph &G）{     //邻接链表创建带权图
	int ijkw;
	VertexType vavb;
	printf（“请输入顶点数边数（请用空格分开）:\n“）; /*输入顶点数、弧数*/
	scanf（“%d   %d“&G.vexnum&G.arcnum）;
	printf（“请输入各顶点的值:\n“）;
	for（i = 0; i < G.vexnum; ++i）  /*初始化顶点值*/
		scanf（“%s“G.vertices[i].data）;
	for（i = 0; i < G.vexnum; ++i）  //初始化vertices数组
	    G.vertices[i].firstarc = NULL;
	printf（“请输入各边的起点终点权值（分别用空格分开）:\n“）;
	for（k = 0; k < G.arcnum; ++k）{
		scanf（“%s%s%d“vavb&w）;
	    i = LocateVe（Gva）;   /*确定va、vb的位置*/
		j = LocateVe（Gvb）;

		ArcNode *p = （ArcNode *）malloc（sizeof（ArcNode））;   //申请一个结点空间

		p->adjvex = j;              //初始化
		p->weight = w;
		p->nextarc = G.vertices[i].firstarc;   //插表头
		G.vertices[i].firstarc = p;

		ArcNode *q = （ArcNode *）malloc（sizeof（ArcNode））;

		q->adjvex = i;
		q->weight = w;
		q->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = q;
	}
} 
/*邻接链表的克鲁斯卡尔算法*/
void kruskal2（ALGraph G）{
	int ijmin = 0x7fffffffk = 0; //min用于记录最小权值
	int set[MAX_VERTEX_NUM];   //用于判断两个点是否在同一集合里
	ArcNode *p*q*s;
	for（i = 0; i < G.vexnum; ++i） set[i] = i; //初始化，将每个点自身作为一个集合
	while（k < G.vexnum - 1）{
		for（i = 0; i < G.vexnum; ++i）{             
			if（G.vertices[i].firstarc != NULL）{    //若第i+1个点没有领边，则下一循环
				for（p = G.vertices[i].firstarc ; p != NULL; p = p->nextarc）   //查找最小权值的边
					if（p->weight < min）{
						min = p->weight;
						q = p;
						j = i;
					}
			}
		}
		if（G.vertices[j].firstarc == q）  G.vertices[j].firstarc = q->