邻接表

补丁牛仔裤 2022-05-14

展开全文

当一个图为稀疏图时，使用邻接矩阵表示显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。
在这里插入图片描述

#define MaxVertexNum 100; //图中顶点数目的最大值
//"边/弧"
typedef struct ArcNode{
    int adjvex; //边/弧指向哪个结点
    struct ArcNode *next; //指向下一条弧的指针
    //InfoType info; //边权值
}ArcNode;
//"顶点"
typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *first; //第一条边/弧
}VNode, AdjList[MaxVertexNum];
//用邻接表存储的图
typedef struct{
    AdjList vertices; //邻接表
    int vexnum, arcnum; //图的顶点数和弧数
}ALGraph; //ALGraph是以邻接表存储图类型

在这里插入图片描述

邻接表

邻接表，是指对图G中的每一个顶点v_i建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v_i 的边（对于有向图则是以顶点v_i为尾的弧），这个单链表就称为顶点v_i的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（成为顶点表），所以在邻接表中存在两种：顶点表结点和边表结点。

顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。
在这里插入图片描述
① 若G为无向图，则所需的存储空间为O(|V|+2|E|)；若G为有向图，则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
② 对于稀疏图，采用邻接表表示将极大地节省存储空间。
③ 在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表。在邻接表矩阵中，相同的操作则需要扫描一行，话费花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中立刻查到，而在邻接表中则需要在相应结点对应的边表中查找另一个结点，效率较低。
④ 在有向图的邻接表表示中，求一个给定顶点的出度只需要计算其邻接表中的结点个数；但求其顶点的入度则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。
⑤ 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链表次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。
在这里插入图片描述