图的邻接表数据结构

[c]代码库

＃define MaxVerNum 100 /*最大顶点数为100*/
typedef struct node  /*边表结点*/
{
	int adjvex; /*邻接点域*/
	struct node * next; /*指向下一个邻接点的指针域*/
	/*若要表示边上信息，则应增加一个数据域info*/
} EdgeNode;
typedef struct vnode  /*顶点表结点*/
{
	VertexType vertex; /*顶点域*/
	EdgeNode * firstedge; /*边表头指针*/
} VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; /*AdjList 是邻接表类型*/
typedef struct
{
	AdjList adjlist; /*邻接表*/
	int n,e; /*顶点数和边数*/
} ALGraph; /*ALGraph 是以邻接表方式存储的图类型*/
建立一个有向图的邻接表存储的算法如下：
void CreateALGraph ( ALGraph *G )
{/*建立有向图的邻接表存储*/
	int i,j,k;
	EdgeNode * s;
	printf ( "请输入顶点数和边数(输入格式为:顶点数,边数)：\n" );
	scanf ( "%d,%d",& ( G->n ),& ( G->e ) ); /*读入顶点数和边数*/
	printf ( "请输入顶点信息(输入格式为:顶点号<CR>)：\n" );
	for ( i=0; i<G->n; i++ ) /*建立有n 个顶点的顶点表*/
	{
		scanf ( "\n%c",& ( G->adjlist[i].vertex ) ); /*读入顶点信息*/
		G->adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/
	}
	printf ( "请输入边的信息(输入格式为:i,j)：\n" );
	for ( k=0; k<G->e; k++ ) /*建立边表*/
	{
		scanf ( "\n%d,%d",&i,&j ); /*读入边<Vi,Vj>的顶点对应序号*/
		s= ( EdgeNode* ) malloc ( sizeof ( EdgeNode ) ); /*生成新边表结点s*/
		s->adjvex=j; /*邻接点序号为j*/
		s->next=G->adjlist[i].firstedge; /*将新边表结点s 插入到顶点Vi 的边表头部*/
		G->adjlist[i].firstedge=s;
	}
}/*CreateALGraph*/