苗火 Nicholas

[Data structures]Minimum cost spanning tree (prim and kruskal)

2019-7-23 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define MAX 20
#define INFINIT	65535

typedef struct _ArcCell{
	int adj; // Weight or flag about connection
	int *info; // Other information
}ArcCell;

typedef char VertexType;

typedef enum{
	DG,
	DN,
	UDG,
	UDN
}GraphKind;

typedef struct _MGraph{
	VertexType vexs[MAX];
	ArcCell arcs[MAX][MAX];
	int vexnum;
	int arcnum;
	GraphKind kind;
}MGraph;

typedef struct _CloseEdge{
	int adjvex;
	int cost;
}CloseEdge;

int visited[MAX];

int LocateVex(MGraph *G, VertexType v)
{
	int i=0;
	while(i<G->vexnum && G->vexs[i] != v){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int CreateUDN(MGraph *G)
{
	int i,j,k;
	char v1,v2;
	int cost;

	scanf(" %d %d", &G->vexnum, &G->arcnum);	
	for(i=0; i<G->vexnum; i++){
		scanf(" %c", &G->vexs[i] );
	}
	for(i=0; i<G->vexnum; i++){
		for(j=0; j<G->vexnum; j++){
			G->arcs[i][j].adj = INFINIT;
		}
	}
	for(k=0; k<G->arcnum; k++){
		scanf(" %c %c %d", &v1, &v2, &cost);
		i=LocateVex(G, v1);
		j=LocateVex(G, v2);	
		G->arcs[i][j].adj = cost;
		G->arcs[j][i].adj = cost;	
	}
	return 1;
}

int FirstAdjvex(MGraph *G, int v)
{
	int i=0;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}	
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int NextAdjvex(MGraph *G, int v, int w)
{
	int i=w+1;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}

}

void Prim(MGraph *G, int u)
{
	int i;
	int j;
	int k;
	int min;
	CloseEdge close[MAX];

	k = u;

	/* Init u set, there is only k in u set, 
	 * and each vertex to k have a definited cost except k itself */
	for(i=0; i<G->vexnum; i++){
		close[i].adjvex = k;
		close[i].cost = G->arcs[k][i].adj;
	}	
	close[k].cost = 0;

	/* It remained n - 1 vertexes not in u set */
	for(i=1; i<G->vexnum; i++){
		/* Find the shortest vertex to u set */
		min = INFINIT;
		for(j=0;j<G->vexnum;j++){
			if(close[j].cost != 0 && min > close[j].cost){
				min = close[j].cost;
				k = j;
			}
		}
		close[k].cost = 0;//Add k to u set

		printf(" %c-%c ", G->vexs[close[k].adjvex], G->vexs[k]);

		/* Refresh the cost */
		for(j=0;j<G->vexnum;j++){
			if(G->arcs[k][j].adj < close[j].cost){
				close[j].cost = G->arcs[k][j].adj;
				close[j].adjvex = k;
			}
		}
	}
}

void Kruskal(MGraph *G)
{
	//TODO:
}



void main()
{
	MGraph G;	

	printf("log.anycle.com\n\n");
	printf("Create graph:\n");
	CreateUDN(&G);
	printf("\n");

	printf("Prim:\n");
	Prim(&G, 0);
	printf("\n");
}

标签: Data Structures data_structures