#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");
}