kruskal.cpp

kruskal算法 很经典的 使用C语言实现

#include <stdio.h>
#include <malloc.h>
#define	Max 10
#define VertexNum 5
struct List
{
	int Vertex1;
	int Vertex2;
	int Weight;
	struct List *Next;
};
typedef struct List Node;
typedef Node *Edge;
int Edges[10][3]={{1,2,7},{1,3,6},{1,4,5},{1,5,12},{2,3,14},{2,4,8},{2,5,8},{3,4,3},{3,5,9},{4,5,2}};
int Visited[VertexNum];

void Kruskal(Edge Head)
{
	Edge Pointer;
	int EdgeNum=0;
	int Weight=0;
	Pointer=Head;
	while(EdgeNum!=(VertexNum-1))
	{
		if(Visited[Pointer->Vertex1]==0||Visited[Pointer->Vertex2]==0)
		{
			printf("==>[%d,%d]",Pointer->Vertex1,Pointer->Vertex2);
			printf("(%d)",Pointer->Weight);
			Weight+=Pointer->Weight;
			EdgeNum++;
			Visited[Pointer->Vertex1]=1;
			Visited[Pointer->Vertex2]=1;
		}
		Pointer=Pointer->Next;
		if(Pointer==NULL)
		{
			printf("No Spanning Tree\n");
			break;
		}
	}
		printf("\nTotal weight = %d\n",Weight);
}

void Print_Edge(Edge Head)
{
	Edge Pointer;
	Pointer=Head;
	while(Pointer!=NULL)
	{
		printf("[%d,%d]",Pointer->Vertex1,Pointer->Vertex2);
		printf("(%d)",Pointer->Weight);
		Pointer=Pointer->Next;
	}
	printf("\n");

}

Edge Insert_Edge(Edge Head,Edge New)
{
	Edge Pointer,p;
	p=Head;
	if(New->Weight<Head->Weight)
	{
		New->Next=Head;
		Head=New;
	}
	else
	{
		while(p!=NULL && New->Weight>=p->Weight)
		{
			Pointer=p;
			p=p->Next;
		}
		Pointer->Next=New;
		New->Next=p;
	}
	
	
	return Head;
}

void Free_Edge(Edge Head)
{
	Edge Pointer;

	while(Head!=NULL)
	{
		Pointer=Head;
		Head=Head->Next;
		free(Pointer);
	}
}
Edge Create_Edge(Edge Head)
{
	Edge New;
	Edge Pointer;
	int i;
	Head=(Edge)malloc(sizeof(Node));
	if(Head==NULL)
	{
		printf("Memory allocate Failure!!\n");
	}
	else
	{
		Head->Vertex1=Edges[0][0];
		Head->Vertex2=Edges[0][1];
		Head->Weight=Edges[0][2];
		Head->Next=NULL;
		for(i=1;i<10;i++)
		{
			New=(Edge)malloc(sizeof(Node));
			if(New!=NULL)
			{
				New->Vertex1=Edges[i][0];
				New->Vertex2=Edges[i][1];
				New->Weight=Edges[i][2];
				New->Next=NULL;
				Head=Insert_Edge(Head,New);
			}
		}
		return Head;
	}
}
void main()
{
	Edge Head;
	int i;
	for(i=0;i<VertexNum;i++)
	{
		Visited[i]=0;
	}
	Head=Create_Edge(Head);
	if(Head!=NULL)
	{
		printf("Kruskal Algorithm :\n");
		printf("First Step : Sorting\n");
		Print_Edge(Head);
		printf("Second Step : Find Minimal Spanning Tree.\n");
		Kruskal(Head);
		Free_Edge(Head);
	}
}