Kruskal算法求最小生成树使用的图的存储结构是图的边表存储结构
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTAX_SIZE 20
#define MAX_EAGE_SIZE 50
#define OK 1
#define ERROR 0
typedef int Status;
typedef char VertaxElemType;
typedef struct EageNode{
int adjacentVertax;
int weight;
struct EageNode* nextEage;
}EageNode,*EageNodePtr;
typedef struct VertaxNode{
VertaxElemType data;
EageNodePtr firstEage;
}VertaxNode;
typedef struct GraphAL{
VertaxNode vertaxNodeArray[MAX_VERTAX_SIZE];
int vertaxNum;
int eageNum;
}GraphAL;
typedef struct EageTableNode{
int eageHead;
int eageTail;
int weight;
}EageTableNode;
typedef struct GraphET{
VertaxElemType vertaxArray[MAX_VERTAX_SIZE];
EageTableNode eageTable[MAX_EAGE_SIZE];
int eageNum;
int vertaxNum;
}GraphET;
int LocateVertax(GraphAL G, VertaxElemType v);
Status CreateGraphAL_UDG_S(GraphAL* G);
Status FromAdjacencyListToEageTable(GraphAL G, GraphET* G_1);
void PrintEageTable(GraphET G);
void PrintAdjacencyList(GraphAL G);
int LocateVertax(GraphAL G, VertaxElemType v){
int i;
for( i = 0; i < G.vertaxNum; i++ ){
if( G.vertaxNodeArray[i].data == v )
return i;
}
return -1;
}
//创建无向图，使用邻接矩阵存储
Status CreateGraphAL_UDG_S(GraphAL* G){//相同的边只存储一次，方便转化为边表结构
int i,index_v,index_w,weight;
VertaxElemType v,w;
EageNodePtr vPtr,wPtr;
printf(" Create UndiGraph with Adjacecy List\n");
printf("please enter the number of VERTAX and EAGE:");
scanf("%d %d%*c", &(G->vertaxNum), &(G->eageNum));
printf("ok, please enter the value of vertaxes,Seperated by Space\n :");
for( i = 0; i < G->vertaxNum; i++ ){
scanf("%c%*c", &(G->vertaxNodeArray[i].data));
G->vertaxNodeArray[i].firstEage = NULL;
}
for( i = 0; i < G->eageNum; i++ ){
printf("ok, please enter the two VERTAX and WEIGHT of EAGE %d\n note: Seperated by Space :", i+1);
scanf("%c %c %d%*c", &v,&w,&weight);
index_v = LocateVertax(*G, v);
index_w = LocateVertax(*G, w);
vPtr = (EageNode*)malloc(sizeof(struct EageNode));
if( !vPtr )
return ERROR;
vPtr->adjacentVertax = index_w;
vPtr->weight = weight;
vPtr->nextEage = G->vertaxNodeArray[index_v].firstEage;
G->vertaxNodeArray[index_v].firstEage = vPtr;
/*
wPtr = (EageNode*)malloc(sizeof(struct EageNode));
if( !wPtr )
return ERROR;
wPtr->adjacentVertax = index_v;
wPtr->weight = weight;
wPtr->nextEage = G->vertaxNodeArray[index_w].firstEage;
G->vertaxNodeArray[index_w].firstEage = wPtr;
*/
}
//PrintAdjacencyList(*G);
return OK;
}
//将图的邻接表表示转化为图的边表表示,kruskal算法将要使用这种结构
Status FromAdjacencyListToEageTable(GraphAL G, GraphET* G_1){
int i,j;
EageNodePtr p;
int counterOfEage = 0;
G_1->eageNum = G.eageNum;
G_1->vertaxNum = G.vertaxNum;
for( i = 0; i < G.vertaxNum; i++ )
G_1->vertaxArray[i] = G.vertaxNodeArray[i].data;
for( i = 0; i < G.vertaxNum; i++ ){
p = G.vertaxNodeArray[i].firstEage;
while( p ){
G_1->eageTable[counterOfEage].eageHead = i;
G_1->eageTable[counterOfEage].eageTail = p->adjacentVertax;
G_1->eageTable[counterOfEage].weight = p->weight;
counterOfEage++;
p = p->nextEage;
}
}
//PrintEageTable(*G_1);
//排序，按权值从小到大
EageTableNode temp;
for( i = 0; i < G_1->eageNum - 1; i++ ){
for( j = i; j < G_1->eageNum; j++ ){
if( G_1->eageTable[i].weight > G_1->eageTable[j].weight ){
temp.eageHead = G_1->eageTable[i].eageHead;
temp.eageTail = G_1->eageTable[i].eageTail;
temp.weight = G_1->eageTable[i].weight;
G_1->eageTable[i].eageHead = G_1->eageTable[j].eageHead;
G_1->eageTable[i].eageTail = G_1->eageTable[j].eageTail;
G_1->eageTable[i].weight = G_1->eageTable[j].weight;
G_1->eageTable[j].eageHead = temp.eageHead;
G_1->eageTable[j].eageTail = temp.eageTail;
G_1->eageTable[j].weight = temp.weight;
}
}
}
if( counterOfEage == G_1->eageNum ){
return OK;
}
else{
return ERROR;
}
}
void PrintEageTable(GraphET G){
int i;
printf("\nPrint Eage Table\n");
printf("--------------------------------------------------\n");
printf("| order | startVertax | endVertax | eageWeight |\n");
for( i = 0; i < G.eageNum; i++ ){
printf("|------------------------------------------------|\n");
printf("| %d | %d | %d | %d |\n", i+1, G.eageTable[i].eageHead, G.eageTable[i].eageTail, G.eageTable[i].weight);
}
printf("--------------------------------------------------\n");
}
void PrintAdjacencyList(GraphAL G){
int i;
EageNodePtr p;
for( i = 0; i < G.vertaxNum; i++ ){
printf(" %d %c : ",i+1, G.vertaxNodeArray[i].data);
p = G.vertaxNodeArray[i].firstEage;
while( p != NULL ){
printf("--->%d weight(%d)", p->adjacentVertax+1,p->weight);
p = p->nextEage;
}
printf("\n");
}
}
int getindex(int* array, int index){
while( array[index] != 0 ){
index = array[index];
}
return index;
}
Status Kruskal(GraphET G){
int i;
int MSTed[MAX_VERTAX_SIZE];//这个数组是Kruskal算法的关键
int v,w;
for( i = 0; i < G.vertaxNum; i++ )
MSTed[i] = 0;
printf("MST(Minimum Cost Spanning Trss) by Kruskal\n");
for( i = 0; i < G.eageNum; i++ ){
v = getindex(MSTed, G.eageTable[i].eageHead);
w = getindex(MSTed, G.eageTable[i].eageTail);
if( v != w ){
printf("(%c, %c) weight(%d)\n", G.vertaxArray[G.eageTable[i].eageHead], G.vertaxArray[G.eageTable[i].eageTail], G.eageTable[i].weight);
MSTed[v] = w;
}
}
return OK;
}
int main(){
GraphAL G;
CreateGraphAL_UDG_S(&G);
GraphET G_1;
FromAdjacencyListToEageTable(G, &G_1);
PrintEageTable(G_1);
Kruskal(G_1);
return OK;
}
