kruskal.cpp

本程序为使用克鲁斯卡尔 (kruskal)算法构造最小生成树

#include "stdio.h"
#define OK 1
#define MAX_VERTEX_NUM  20 
#define INFINITY  9999   
typedef struct 
{
	char begin;
	char end;
	int weight;
}edge;

struct closedge 
{
     char  adjvex;  // U集中的顶点序号
     int  lowcost;  // 边的权值
} closedge[MAX_VERTEX_NUM];
typedef struct ArcCell
{ 
     int  adj;  
	 int  weight;
} ArcCell, AdjMatrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{                      
	char  vexs[MAX_VERTEX_NUM]; 
	int visited[MAX_VERTEX_NUM];
	AdjMatrix  arcs;                   
	int  vexnum, arcnum;          
} MGraph;
MGraph G1;
int LocateVex(MGraph G, char v)
{
	int i = 0,j =0;
	for(i = 0;i < G.vexnum;++i)
		if(G.vexs[i] == v)
			j = i;
	return j;
}
int Creat(MGraph &G)
{
	int i = 0,j = 0,k = 0,w = 0;
	char v1,v2;
	printf("请输入(连通)图的相关信息:(当前顶点数，弧数)\n");
	scanf("%d,%d",&G.vexnum,&G.arcnum);
	fflush(stdin);
	printf("请输入图中包含的所有结点:\n");
	for(i = 0;i < G.vexnum;i++)
	{
		scanf("%c",&G.vexs[i]);
		fflush(stdin);
		G.visited[i] = 0;
	}
    for(i = 0;i < G.vexnum;++i)
		for(j = 0;j < G.vexnum;++j)
			G.arcs[i][j].adj= 0;
	printf("请输入各弧:(顶点v1,顶点v2,权值w)\n");
    for(k = 0;k < G.arcnum;++k)
	{
		scanf("%c,%c,%d",&v1,&v2,&w);
		fflush(stdin);
		i = LocateVex(G,v1);
		j = LocateVex(G,v2);
		G.arcs[j][i].adj = G.arcs[i][j].adj = 1;
		G.arcs[j][i].weight = G.arcs[i][j].weight = w;
	}
	return OK;
}
void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾 
{  
	char temp; 
	int n;
	temp = edges[i].begin;  
	edges[i].begin = edges[j].begin;
    edges[j].begin = temp;
    temp = edges[i].end;  
    edges[i].end = edges[j].end;
    edges[j].end = temp;
    n = edges[i].weight;  
    edges[i].weight = edges[j].weight;
    edges[j].weight = n;
}
void sort(edge edges[],MGraph G)//对权值进行排序 
{
	int i, j;
	for ( i = 0; i < G.arcnum - 1; i++)
	{
		for ( j = i + 1; j < G.arcnum; j++)
		{
			if (edges[i].weight > edges[j].weight)
			{
				Swapn(edges, i, j);
			}
		}
	}
	printf("权排序之后的为:\n");
	for (i = 0; i < G.arcnum; i++)
	{
		printf("( %c, %c )   %d\n", edges[i].begin, edges[i].end, edges[i].weight);
	}

}
int Find(int *parent, char f)//找尾 
{
	int i = 0;
	i = LocateVex(G1,f); 
	while (parent[i] > 0)
	{
		i = parent[i];
	}
	return i;
}
void MiniSpanTree_P(MGraph G, char u)
{
	int i, j, n, m;
	int k = 0;
    int parent[MAX_VERTEX_NUM];
	edge edges[MAX_VERTEX_NUM];
	for (i = 0;i < G.vexnum - 1;i++)
	{
		for (j = i + 1;j < G.vexnum;j++)
		{
			if (G.arcs[i][j].adj == 1)
			{
				edges[k].begin = G.vexs[i];
				edges[k].end = G.vexs[j];
				edges[k].weight = G.arcs[i][j].weight;
				k++;
			}
		}
	}
	sort(edges, G);
	for (i = 0;i < G.arcnum;i++)
	{
		parent[i] = 0;
	}
	printf("最小生成树为:\n");
	for (i = 0; i < G.arcnum; i++)//核心部分 
	{
		n = Find(parent, edges[i].begin);
		m = Find(parent, edges[i].end);
		if (n != m)
		{
			parent[n] = m;
			int l = 0;
			l = LocateVex(G,edges[i].begin); 
			if(G.visited[l] == 0)
			{
				printf("%4c", edges[i].begin);
				G.visited[l] = 1;
			}
			l = LocateVex(G,edges[i].end); 
			if(G.visited[l] == 0)
			{
				printf("%4c", edges[i].end);
				G.visited[l] = 1;
			}
		}
	}
}
int main(int argc, char* argv[])
{
	char v1;
	Creat(G1);
	printf("请输入根结点:\n");
	scanf("%c",&v1);
	fflush(stdin);
	MiniSpanTree_P(G1,v1);
	printf("\n");
	return 0;
}