[图](4)邻接表存储结构

邻接表(链式表示法)

邻接表(Adjacency List)是图的一种链式存储结构,在邻接表中,对图中每个顶点建立一个单链表,第 i 个单链表中的结点表示依附于顶点 vi 的边(对有向图是以顶点vi为尾的弧)。

每个结点由三个域组成,其中邻接点域(adjvex)指示与顶点vi邻接的点在图中的位置,链域(nextarc)指示下一条边或弧的结点,数据域(info)存储的边或弧相关的信息,如权值等

每个链表上附设一表头结点,在表头结点中,除了设有链域(firstarc)指向链表中的第一个结点之外,还设有存储顶点vi的名或其他有关信息的数据域(data),如下图所示:

从上述可知:

  • 顶点:按编号顺序将顶点数据存储在一维数组中
  • 关联同一顶点的边(以顶点为尾的弧):用线性链表存储

无向图邻接表

image-20210124115659968

上述图例未使用info域

特点:

  • 邻接表不唯一(边的顺序可变,结点顺序不唯一)
  • 若无向图中有n个顶点、e条边,则其邻接表需n个头结点和2e个表结点,适宜存储稀疏图
  • 无向图中顶点vi的度为第i个单链表中的结点数

有向图邻接表

在无向图当中,每条边都需要保存两次,而在有向图当中,即只需要保存一次,保存以当前顶点为弧尾的边 (即单链表中存储的是其出度边)

image-20210124121051234

特点:

  • 表头结点表是有顶点表构成的,其后链接的单链表为其出度边
  • 顶点vi的出度为第i个单链表中的结点个数
  • 顶点vi的入度为整个单链表中邻接域值是i-1的结点个数
  • 从上所述:计算出度很容易,但是找其出度难

逆邻接表

我们之前是存储每个结点的出度边,当然,我们也可以在单链表中存储其入度边。而存储入度边的邻接表我们称为逆邻接表,如上图所示的G图的逆邻接表如下所示:

image-20210124122701262

特点:

  • 顶点vi的入度为第 i 个单链表的结点个数
  • 顶点vi的出度为整个单链表中邻接点域值是 i - 1 的结点个数
  • 则其找入度容易,找出度难

对于邻接表和逆邻接表,我们需要根据实际情况应用求得

当邻接表的存储结构形成后,图便可以唯一确定

建立邻接表

其抽象数据类型定义如下所示:

//-----图的邻接表存储表示---
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
    int adjvex;//该弧所指向的顶点的位置
    struct ArcNode* nextarc;//指向下一条弧的指针
    InfoType* info;//该弧相关信息的指针
}ArcNode;
typedef struct VNode {
    VertexType data;//顶点信息
    ArcNode* firstarc;//指向第一条依附该顶点的弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
    GraphKind Kind;
}ALGraph;

我们依旧拿创建无向网的思想做一个笔记,算法思想如下所示:

  1. 输入总顶点数总边数
  2. 建立顶点表

    1. 依次输入点的信息存入顶点表中
    2. 使每个表头结点的指针域初始化为NULL
  3. 创建邻接表

    1. 依次输入每条边依附的两个顶点
    2. 确定两个顶点的序号 i 和 j ,建立边结点
    3. 将此边结点分别插入到 vi 和 vj 对应的两个边链表的头部

算法如下所示:

int LocateVex(ALGraph G, char e) {
    for (int i = 0; i < G.vexnum; i++)
        if (G.vertices[i].data == e) return i;
    return -1;
}
Status Print_UDN_UDGALGraph(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        printf("%c:", G.vertices[i].data);
        ArcNode* p = G.vertices[i].firstarc;
        while (p) {
            printf("[%d,%d]->", p->adjvex, *(p->info));
            p = p->nextarc;
        }
        printf("\n");
    }
    return OK;
}
//以邻接表方式创建无向网
Status CreateUDN(ALGraph* G) {
    char tem;//为输入方便,过滤换行符
    scanf("%d,%d%c", &G->vexnum, &G->arcnum, &tem);//确定顶点数和边数

    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c%c", &G->vertices[i].data, &tem);//构造顶点表
        G->vertices[i].firstarc = NULL;//初始化链域
    }
    char v1, v2;
    int In, Out, weight;//弧尾,弧头,权值
    ArcNode* p1, * p2;
    
    for (int j = 0; j < G->arcnum; j++) {
        printf("Input Arc Info:");
        scanf("%c,%c,%d%c", &v1, &v2, &weight, &tem);//输入边两端的顶点以及该边的权值
        
        In = LocateVex(*G, v1);//找出与该边相关联顶点在顶点集里的位置
        Out = LocateVex(*G, v2);
        if (In == Out == -1)return ERROR;

        //创建表结点
        p1 = (ArcNode*)malloc(sizeof(ArcNode));
        p1->adjvex = In;
        p1->info = (InfoType*)malloc(sizeof(InfoType));
        (*p1->info) = weight;
        p1->nextarc = G->vertices[Out].firstarc;
        G->vertices[Out].firstarc = p1;

        p2 = (ArcNode*)malloc(sizeof(ArcNode));
        p2->adjvex = Out;
        p2->info = (InfoType*)malloc(sizeof(InfoType));
        (*p2->info) = weight;
        p2->nextarc = G->vertices[In].firstarc;
        G->vertices[In].firstarc = p2;
    }
    Print_UDN_UDGALGraph(*G);//打印检查
    return OK;
}

邻接表与邻接矩阵的关系

邻接表的优缺点:
  • 方便找任一顶点的所有“邻接点”
  • 节约稀疏图的空间

    • 需要N个头指针+2E个结点(每个结点至少2个域)
  • 方便计算无向图任一顶点的“度”
  • 对于有向图计算度则需要根据需要建立邻接表(方便计算出度)逆邻接表(方便计算入度)
  • 不方便检查任一一对顶点间是否存在边
邻接表与邻接矩阵的关系
  • 联系:邻接表中每个链表对应于邻接矩阵中的一行,链表中结点个数等于一行中非零元素的个数
  • 区别

    • 对于任一确定的无向图,邻接矩阵是唯一的(行列号与顶点编号一致),但邻接表不唯一(链接次序与顶点编号无关)
    • 邻接矩阵的空间复杂度O(n²),而邻接表的空间复杂度为O(n+e)
  • 用途:邻接矩阵多用于稠密图;而邻接表多用于稀疏图

本文链接:

https://nullcode.fun/127.html
1 + 1 =
快来做第一个评论的人吧~