#include "stdio.h"
#include <stdlib.h>
#define MaxVertexNum 100
typedef enum{FALSE,TRUE}Boolean;/*FALSE為0,tRUE為1*/
Boolean visited[MaxVertexNum];
typedef int Vertextype;
typedef struct node{/*邊表結(jié)點(diǎn)*/
	int adjvex; /*鄰接點(diǎn)域*/
	struct node *next; /*鏈域*/
	/*若要表示邊上的權(quán),則應(yīng)增加一個(gè)數(shù)據(jù)域*/
}EdgeNode;
typedef struct vnode{ /*頂點(diǎn)表結(jié)點(diǎn)*/
	Vertextype vertex; /*頂點(diǎn)域*/
	EdgeNode *firstedge;/*邊表頭指針*/
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum];/*AdjList是鄰接表類型*/
typedef struct ALGraph{
	AdjList adjlist;/*鄰接表*/
	int n,e; /*圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
}Graphic; /*對(duì)于簡單的應(yīng)用,無須定義此類型,可直接使用AdjList類型。*/
typedef struct tree
{
	VertexNode * tnode;
	EdgeNode *tedge;
}MSt;
MSt *mst;
void CreateGraphic(Graphic *G)
{/*建立無向圖的鄰接表表示*/
     	int i,j,k;
      	EdgeNode *s;
      	scanf("%d%d",&G->n,&G->e); /*讀人頂點(diǎn)數(shù)和邊數(shù)*/
      	for(i=0;i<G->n;i++){/*建立頂點(diǎn)表*/
        	G->adjlist[i].vertex=getchar(); /*讀入頂點(diǎn)信息*/
        	G->adjlist[i].firstedge=NULL;/*邊表置為空表*/
       	}
      	for(k=0;k<G->e;k++){/*建立邊表*/
         	scanf("%d%d",&i,&j);/*讀入邊(vi,vj)的頂點(diǎn)對(duì)序號(hào)*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode)); /*生成邊表結(jié)點(diǎn)*/
         	s->adjvex=j; /*鄰接點(diǎn)序號(hào)為j*/
         	s->next=G->adjlist[i].firstedge;
 	        G->adjlist[i].firstedge=s; /*將新結(jié)點(diǎn)*s插入頂點(diǎn)vi的邊表頭部*/
         	s=(EdgeNode *)malloc(sizeof(EdgeNode));
         	s->adjvex=i; /*鄰接點(diǎn)序號(hào)為i*/
         	s->next=G->adjlist[j].firstedge;
         	G->adjlist[j].firstedge=s; /*將新結(jié)點(diǎn)*s插入頂點(diǎn)vj的邊表頭部*/
        }   
} 

void PrimMST(Graphic *G,Vertextype r)
{	/*求圖G的以r為根的MST,結(jié)果放在T=(U,TE)中*/
	int k,n;
    	/*InitCandidateSet(…)初始始化：設(shè)置初始的輕邊候選集,并置T=({r},￠)*/
    for(k=0;k<n-1;k++){ /*求T的n-1條樹邊*/
        	//(u,v)=SelectLiShtEdge(…);/*選取輕邊(u,v);*/
        	//	T←T∪{(u,v)};/*擴(kuò)充T,即(u,v)涂紅加入TE,藍(lán)點(diǎn)v并人紅點(diǎn)集U*/
        	//ModifyCandidateSet(…); /*根據(jù)新紅點(diǎn)v調(diào)整候選輕邊集*/
    }  
}

void main(void)
{
	Graphic graph;
	Vertextype r=3;
	CreateGraphic(&graph);
	PrimMST(&graph,r);
}