图的邻接表存储结构及求各顶点的度
数组与链表相结合的存储方法称为邻接表（Adjacency List）
邻接表的处理方法是：
1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数组元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2.图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点Vi的边表，有向图称为顶点Vi作为弧尾的出边表。
获取图的相关信息：
1.我们要想知道某个顶点的度，就去查找这个顶点的边表中节点的个数。
2.要判断顶点Vi到Vj是否存在边，只需要测试顶点Vi的边表中adjvex是否存在节点Vj的下标j就行了。
3.求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。
对于有向图，邻接表是以顶点为弧尾来存储边表的，逆邻接表是以顶点为弧头来存储边表的。
无向图的邻接表结构：
有向图的邻接表及逆邻接表结构：
对于带权的网图，可以在边表节点定义中再增加一个weight的数据域，存储权值信息即可：
下面的程序就是利用图的邻接表存储结构，实现计算无向图的各个顶点的度数(C/C++)：
/*********************************************/
/* 邻接表存储结构 */
/*********************************************/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define M 20 //预定义图的最大顶点数
typedef char DataType; //顶点信息数据类型
typedef struct node{ //边表结点
int adjvex; //邻接点
struct node *next;
}EdgeNode;
typedef struct vnode{ //头结点类型
DataType vertex; //顶点信息
EdgeNode *FirstEdge; //邻接链表头指针
}VertexNode;
typedef struct{ //邻接表类型
VertexNode adjlist[M]; //存放头结点的顺序表
int n,e; //图的顶点数与边数
}LinkedGraph;
/*
函数功能：建立图的邻接表
函数参数：邻接表指针变量g；
存放图信息的文件名filename;
图的类型参数c，c=0表示建立无向图，否则表示建立有向图
函数返回值：无
*/
void creat(LinkedGraph *g,char *filename,int c)
{
int i,j,k;
EdgeNode *s;
FILE *fp;
fp=fopen(filename,"r");
if (fp)
{
fscanf(fp,"%d%d",&g->n,&g->e); //读入顶点数与边数
for(i=0;i<g->n;i++)
{
fscanf(fp,"%1s",&g->adjlist[i].vertex); //读入顶点信息
g->adjlist[i].FirstEdge=NULL; //边表置为空表
}
for(k=0;k<g->e;k++) //循环e次建立边表
{
fscanf(fp,"%d%d",&i,&j); // 输入无序对（i,j）
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=j; //邻接点序号为j
s->next=g->adjlist[i].FirstEdge;
g->adjlist[i].FirstEdge=s; //将新结点*s插入顶点vi的边表头部
if (c==0) //无向图
{
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //邻接点序号为i
s->next=g->adjlist[j].FirstEdge;
g->adjlist[j].FirstEdge=s; //将新结点*s插入顶点vj的边表头部
}
}
fclose(fp);
}
else
g->n=0;
}
//函数print():输出邻接表存储结构
void print(LinkedGraph g)
{
EdgeNode *p;
int i;
for (i=0;i<g.n;i++)
{
printf("%c",g.adjlist[i].vertex);
p=g.adjlist[i].FirstEdge;
while (p)
{
printf("-->%d",p->adjvex);
p=p->next;
}
printf("\n");
}
}
//函数weight():输出无向图各顶点的度数
void weight(LinkedGraph g)
{
EdgeNode *p;
int n,i;
for (i=0;i<g.n;i++)
{
n=0;
p=g.adjlist[i].FirstEdge;
while (p)
{
n++;
p=p->next;
}
cout<<i<<":"<<n<<endl;
//printf("%d:%d\n",i,n);
}
}
int main()
{
LinkedGraph * Grap=newLinkedGraph;
creat(Grap,"G11.TXT",0);
print(*Grap);
weight(*Grap);
delete Grap;
/*
LinkedGraph g;
creat(&g,"G11.TXT",0);
print(g);
weight(g);
*/
return 0;
}