图的邻接表

邻接矩阵用二维数组即可存取,比较简单,但除完全图外,一般的图不是任意两个顶点都相邻接,因此邻接矩阵也有很多零元素,特别是当n 较大而边数相对完全图的边(n-1)又少得多时,邻接矩阵仍是很稀疏,这样浪费存储空间。

邻接表(Adjacency List)是图的一种顺序存储与链式存储结合的存储方法，类似于树的孩子链表表示法。由于它只考虑非零元素,因而节省了零元素所占的存储空间。它对于无向图和有向图都适用。

邻接表示法就是对于图G中的每个顶点放到一个数组中，数组的每个元素存放一个结点并指向一个单链表的指针。链表中存储着与该顶点相邻接的顶点所在的数组元素的下标。在邻接表表示中有两种编程结点结构，如图6-9所示。



(a) 表头结点 (b) 边表结点

图6-9邻接矩阵表示的结点结构

在邻接表中，对图中每个顶点建立一个单链表。单链表有一个表头结点，表头结点的结构为图6-9（a）所示。其中，vertex域存放图中某个顶点vi 的信息，link为指针，指向对应单链表中的结点。

单链表中的结点称为边表结点，边表结点结构如图6-9（b）所示。其中，adjvex域存放与顶点vi相邻接的顶点在二维数组中的序号，next域为指针，指向与顶点vi相邻接的下一个顶点的边表结点。

下图6-10给出无向图6-7对应的邻接表表示。



图6-10图的邻接表表示

邻接表表示的形式描述如下：

结构6-2 邻接表的结构

C语言代码

#define maxvernum 100    //最大顶点数为100

typedef struct node     //边表结点

{
    int adjvex;       //邻接点域

    struct node* next;    //指向下一个邻接点的指针域

}Edgenode;       

typedef struct vnode    //表头结点

{
    Vertextype vertex;    //顶点域

    Edgenode*link;  //边表头指针

} Vexnode;   

typedef Vexnode adjlist[maxvernum];//adjlist是邻接表类型

typedef struct

{
    adjlist adjlist;       //邻接表

    int n,e;         //顶点数和边数

} Adjgraph;     // Adjgraph是以邻接表方式存储的图类型 

建立一个有向图的邻接表存储的算法如下：

算法6-2 建立邻接表的算法

void greatealgraph(Adjgraph *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].link=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插入到顶点vi的边表头部

        s->next=g->adjlist[i].link;  

        g->adjlist[i].link=s;

  }
}