#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?		scanf（“%s“G.vertices[i].data）;
	for（i?=?0;?i?	????G.vertices[i].firstarc?=?NULL;
	printf（“請輸入各邊的起點終點權值（分別用空格分開）:\n“）;
	for（k?=?0;?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?	while（k?		for（i?=?0;?i?			if（G.vertices[i].firstarc?!=?NULL）{????//若第i+1個點沒有領邊，則下一循環
				for（p?=?G.vertices[i].firstarc?;?p?!=?NULL;?p?=?p->nextarc）???//查找最小權值的邊
					if（p->weight?						min?=?p->weight;
						q?=?p;
						j?=?i;
					}
			}
		}
		if（G.vertices[j].firstarc?==?q）??G.vertices[j].firstarc?=?q->