圖的鄰接表存儲 c實作

                       圖的鄰接表存儲 c實作 （轉載）

用到的資料結構是

一個是頂點表，包括頂點和指向下一個鄰接點的指針

一個是邊表， 資料結構跟頂點不同，存儲的是頂點的序号，和指向下一個的指針

剛開始的時候把頂點表初始化，指針指向null。然後邊表插入進來，是插入到前一個，也就是直接插入到firstedge指向的下一個，而後面的後移

#define  MaxVertexNum 100

typedef char VertexType;
typedef struct node   //邊表節點
{
   int adjvex;
   node* next;
}EdgeNode;

typedef struct     //頂點表節點
{
   VertexType vertex;
   EdgeNode* firstedge;
}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct 
{ 
	AdjList adjlist;
	int n,e;

}ALGraph;      

以下建立的是無向圖的鄰接表，有向圖的更簡單了

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

#define  MaxVertexNum 100

typedef char VertexType;
typedef struct node   //邊表節點
{
   int adjvex;
   node* next;
}EdgeNode;

typedef struct     //頂點表節點
{
   VertexType vertex;
   EdgeNode* firstedge;
}VertexNode;

typedef VertexNode AdjList[MaxVertexNum];

typedef struct 
{ 
	AdjList adjlist;
	int n,e;

}ALGraph;

void create(ALGraph*);

void main()
{
   ALGraph* G= (ALGraph*)malloc(sizeof(ALGraph));
   create(G);
   for (int i=0;i< G->n;i++)
   {
	   printf("%d->",i);
	   while(G->adjlist[i].firstedge!=NULL)
	   {
			printf("%d->",G->adjlist[i].firstedge->adjvex);
			G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;

	   }
	   printf("\n");
   }
}
void create(ALGraph* G)
{
    int i,j,k,w,v;
    EdgeNode *s;
	printf("讀入頂點數和邊數");
    scanf("%d,%d",&G->n,&G->e);

  
   for (i=0;i<G->n;i++)
   {
	   fflush(stdin);
	   printf("建立頂點表");
	   G->adjlist[i].vertex=getchar();
	   G->adjlist[i].firstedge=NULL;
   }
   printf("建立邊表\n");
   for (k=0;k<G->e;k++)
   {
	   printf("讀入(vi-vj)的頂點對序号");
	   scanf("%d,%d",&i,&j);
	   s=(EdgeNode*)malloc(sizeof(EdgeNode));
	   s->adjvex=j;
	   s->next=G->adjlist[i].firstedge;  //插入表頭
	   G->adjlist[i].firstedge=s;
	   s=(EdgeNode*)malloc(sizeof(EdgeNode));
	   s->adjvex=i;
	   s->next=G->adjlist[j].firstedge;
	   G->adjlist[j].firstedge=s;

   }
}