作者：解学武

图的邻接多重表存储结构（C语言实现）

图的十字链表存储结构 深度优先搜索（DFS）算法
上一节 下一节
存储无向图（网），既可以使用邻接表结构，也可以使用本节讲解的邻接多重表结构。

以图 1a) 的无向图为例，如果用邻接表存储它，存储状态如图 1b) 所示：

邻接表存储无向图
图 1 邻接表存储无向图
观察图 1b) 的邻接表：
  • V1 的链表中有两个结点，记录着 (V1, V2) 和 (V1, V4) 这两条边；
  • V2 的链表中有三个结点，记录着 (V2, V1)、(V2, V3) 和 (V2, V5) 这三条边；
  • V3 的链表中有三个结点，记录着 (V3, V2)、(V3, V4) 和 (V3, V5) 这三条边；
  • V4 的链表中有两个结点，记录着 (V4, V1) 和 (V4, V3) 这两条边；
  • V5 的链表中有两个结点，记录着 (V5, V3) 和 (V5, V2) 这两条边。

在无向图里，(Vi, Vj) 和 (Vj, Vi) 表示的其实是同一条边，比如 (V1, V2) 和 (V2, V1) 就是同一条边。无向图的邻接表存储结构中，每条边都会存储两份，比如我们可以在 V1 顶点的链表中找到 (V1, V2) 这条边，也可以在 V2 的链表中找到 (V2, V1) 这条边。

实际场景中，如果需要对无向图中的边做大量的插入或删除操作，不推荐使用邻接表存储结构，因为每条边在邻接表都存有两份，同样的操作需要处理两次。这种情况下，可以优先考虑邻接多重表存储结构。

邻接多重表是什么

邻接多重表（Adjacency Multilist）是一种专门存储无向图（网）的结构。

邻接多重表存储无向图的方式，可以看作是邻接表和十字链表的结合体，具体来讲就是：将图中的所有顶点存储到顺序表（也可以用链表）中，同时为每个顶点配备一个链表，链表的各个结点中存储的都是和当前顶点有直接关联的边。

举个简单的例子，用邻接多重表存储图 1a) 的无向图，存储状态如下图所示：

邻接多重表存储无向图
图 2 邻接多重表存储无向图

观察图 2b)，顺序表的各个存储空间分为 2 部分，链表中的结点空间分为 5 部分。

顺序表用来存储图中的各个顶点，各个存储空间的结构如下图所示：

顺序表中存储空间的结构
图 3 顺序表中存储空间的结构

data 数据域用来存储顶点的数据；firstedge 指针域用来指向为当前顶点配备的链表。

邻接多重表中的链表用来存储和当前顶点有直接关联的边，结点的结构如下图所示：

链表中的结点结构
图 4 链表中的结点结构

各个部分的含义分别是：
  • mark 标志域：实际场景中，可以为每个结点设置一个标志域，记录当前结点是否已经被操作过。例如遍历无向图中的所有边，借助 mark 标志域可以避免重复访问同一条边；
  • ivex 和 jvec：都是数据域，分别存储边两端顶点所在顺序表中的位置下标；
  • ilink 指针域：指向下一个与 ivex 顶点有直接关联的边结点；
  • jlink 指针域：指向下一个与 jvex 顶点有直接关联的边节点；
  • info 指针域：存储当前边的其它信息，比如存储无向网时，可以用 info 指针域存储边的权值。

在邻接多重表中，很容易可以找到和目标顶点有直接关联的所有边。以图 3 中的 V1 顶点为例，在邻接多重表中查找和它直接关联的边，具体过程是：
  • 根据 V1 顶点的 firstedge 指针域，找到第一个和 V1 有直接关联的边结点 (V1, V2)；
  • 在 (V1, V2) 边结点中，ivex 数据域存储着 V1 顶点对应的顺序表下标，因此继续根据 ilink 指针域找到下一个边结点 (V1, V4);
  • 在 (V1, V4) 边结点中，ivex 数据域存储着 V1 顶点对应的顺序表下标，但 ilink 指针域为 NULL，因此查找结束；

对比图 1 和图 2 不难发现，邻接多重表和邻接表最大的不同是：对于无向图中的每个边，邻接表需要存储两份数据，而邻接多重表只需要存储一份。因此，当需要在无向图中做大量的插入或删除边的操作时，选用邻接多重表存储无向图，可以提高程序的执行效率。

构建无向图的邻接多重表结构，对应的 C 语言代码为： 
#define MAX_VERTEX_NUM 20                      //图中顶点的最大数量
#define InfoType int*                          //边结点中info域的数据类型
#define VertexType int                         //顶点的数据类型
typedef enum { unvisited, visited }VisitIf;    //边标志域
//表示链表中的各个结点
typedef struct EBox {
    VisitIf mark;                            //标志域
    int ivex, jvex;                          //边两边顶点在顺序表中的位置下标
    struct EBox* ilink, * jlink;             //分别指向与ivex、jvex相关的下一个边结点
    InfoType* info;                          //边的其它信息
}EBox;
//存储图中的各个顶点
typedef struct VexBox {
    VertexType data;                        //顶点数据域
    EBox* firstedge;                        //指向当前顶点对应的链表
}VexBox;
//表示邻接多重表结构
typedef struct {
    VexBox adjmulist[MAX_VERTEX_NUM]; //存储图中顶点的顺序表
    int vexnum, edgenum;              //记录图中的顶点数量和边数量
}AMLGraph;

可以根据实现场景的需要，可以修改结构体中各个成员的数据类型，必要时还可以对某些成员进行删减，怎么方便怎么来。

邻接多重表的具体实现

如下是一个完整的 C 语言程序，实现了邻接多重表结构的创建和删除，以及对无向图中指定边的插入和删除操作，附带详尽的代码注释。
#include<stdio.h>
#define MAX_VERTEX_NUM 20                      //图中顶点的最大数量
#define VertexType char                         //顶点的数据类型
#define Status int                             //设定一些函数的返回值类型
typedef enum { unvisited, visited }VisitIf;    //边标志域
//表示链表中的各个结点
typedef struct EBox {
    VisitIf mark;                            //标志域
    int ivex, jvex;                          //边两边顶点在顺序表中的位置下标
    struct EBox* ilink, * jlink;             //分别指向与ivex、jvex相关的下一个边结点
}EBox;
//存储图中的各个顶点
typedef struct VexBox {
    VertexType data;                        //顶点数据域
    EBox* firstedge;                        //指向当前顶点对应的链表
}VexBox;
//表示邻接多重表结构
typedef struct {
    VexBox adjmulist[MAX_VERTEX_NUM]; //存储图中顶点的顺序表
    int vexnum, edgenum;              //记录图中的顶点数量和边数量
}AMLGraph;
//获取 v 顶点在顺序表中的位置下标
int LocateVex(AMLGraph* G, VertexType v);
//创建邻接多重表
Status CreateDN(AMLGraph* G);
//将(V1,V2)插入到邻接多重表中
Status InsertEdge(AMLGraph* G, VertexType V1, VertexType V2);
//从邻接多重表中删除 (V1,V2)或者(V2,V1)
Status DeleteEdge(AMLGraph* G, VertexType V1, VertexType V2);
//输出邻接多重表中包含的所有边
void PrintEdges(AMLGraph* G);
//重置各个结点中的标志域
void InitMarks(AMLGraph* G);
//释放邻接多重表中申请的堆空间
Status DeleteDN(AMLGraph* G);

int main() {
    AMLGraph G;
    CreateDN(&G);
    PrintEdges(&G);
    printf("删除 A-B 边：\n");
    DeleteEdge(&G, 'A', 'B');
    PrintEdges(&G);
    DeleteDN(&G);
    return 0;
}

int LocateVex(AMLGraph* G, VertexType v) {
    int i;
    //遍历一维数组，找到变量v
    for (i = 0; i < G->vexnum; i++) {
        if (G->adjmulist[i].data == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i > G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}

Status CreateDN(AMLGraph* G) {
    int i, j, k;
    VertexType V1, V2;
    //输入无向图的顶点数和边数
    scanf("%d %d", &(G->vexnum), &(G->edgenum));
    getchar();
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (i = 0; i < G->vexnum; i++) {
        scanf("%c", &(G->adjmulist[i].data));
        getchar();
        G->adjmulist[i].firstedge = NULL;
    }
    //存储图中的所有边
    for (k = 0; k < G->edgenum; k++) {
        scanf("%c %c", &V1, &V2);
        getchar();
        InsertEdge(G, V1, V2);
    }
    return 1;
}

Status InsertEdge(AMLGraph* G, VertexType V1, VertexType V2) {
   int V1Add = LocateVex(G, V1);
   int V2Add = LocateVex(G, V2);
   EBox* node = NULL, * p = NULL, * q = NULL;
   if (V1Add < 0 || V2Add < 0) {
       printf("输入边信息有误\n");
       exit(-1);
   }
   //构建一个新结点
   node = (EBox*)malloc(sizeof(EBox));
   node->mark = unvisited;
   node->ivex = V1Add;
   node->jvex = V2Add;
   //用头插法，将 node 结点链接到 V1 顶点的链表中
   node->ilink = G->adjmulist[V1Add].firstedge;
   G->adjmulist[V1Add].firstedge = node;
   //用头插法，将 node 结点链接到 V2 顶点的链表中
   node->jlink = G->adjmulist[V2Add].firstedge;
   G->adjmulist[V2Add].firstedge = node;
   return 1;
}
/*
* 删除(V1,V2) 或者(V2,V1)
* 实现思路：
* 1、从 V1 顶点的链表出发，找到目标结点的直接前驱结点；
* 2、从 V2 顶点的链表触发，找到目标结点的直接前驱结点；
* 3、将目标结点从 V1 顶点的链表中摘除，从 V2 顶点的链表中摘除
* 4、删除目标结点
*/
Status DeleteEdge(AMLGraph* G, VertexType V1, VertexType V2) {
    int V1Add = LocateVex(G, V1);
    int V2Add = LocateVex(G, V2);
    EBox* icurNode = NULL, * ipreNode = NULL;
    EBox* jcurNode = NULL, * jpreNode = NULL;

    //1、从 V1 顶点的链表出发，找到目标结点的直接前驱结点；
    icurNode = G->adjmulist[V1Add].firstedge;
    while (icurNode && !(((icurNode->ivex == V1Add) && (icurNode->jvex == V2Add)) || ((icurNode->ivex == V2Add) && (icurNode->jvex == V1Add)))) {
        ipreNode = icurNode;
        if (icurNode->ivex == V1Add) {
            icurNode = icurNode->ilink;
        }
        else
        {
            icurNode = icurNode->jlink;
        }
    }
    if (!icurNode) {
        printf("指定的边不存在，失败操作失败\n");
        return -1;
    }
   
    //2、从 V2 顶点的链表触发，找到目标结点的直接前驱结点；
    jcurNode = G->adjmulist[V2Add].firstedge;
    while (jcurNode && !(((jcurNode->ivex == V1Add) && (jcurNode->jvex == V2Add)) || ((jcurNode->ivex == V2Add) && (jcurNode->jvex == V1Add)))) {
        jpreNode = jcurNode;
        if (jcurNode->ivex == V2Add) {
            jcurNode = jcurNode->ilink;
        }
        else
        {
            jcurNode = jcurNode->jlink;
        }
    }
    if (!jcurNode) {
        printf("指定的边不存在，失败操作失败\n");
        return -1;
    }
    //3、将目标结点从 V1 顶点的链表中摘除
    if (ipreNode == NULL) {
        if (icurNode->ivex == V1Add) {
            G->adjmulist[V1Add].firstedge = icurNode->ilink;
        }
        else
        {
            G->adjmulist[V1Add].firstedge = icurNode->jlink;
        }
    }
    else
    {
        if (ipreNode->ivex == V1Add) {
            if (icurNode->ivex == V1Add) {
               ipreNode->ilink = icurNode->ilink;
            }
            else
            {
                ipreNode->ilink = icurNode->jlink;
            }
        }
        else
        {
            if (icurNode->ivex == V1Add) {
                ipreNode->jlink = icurNode->ilink;
            }
            else
            {
                ipreNode->jlink = icurNode->jlink;
            }
        }   
    }
    //3、将目标结点从 V2 顶点的链表中摘除
    if (jpreNode == NULL) {
        if (jcurNode->ivex == V2Add) {
            G->adjmulist[V2Add].firstedge = jcurNode->ilink;
        }
        else
        {
            G->adjmulist[V2Add].firstedge = jcurNode->jlink;
        }
    }
    else
    {
        if (jpreNode->ivex == V2Add) {
            if (jcurNode->ivex == V2Add) {
                jpreNode->ilink = jcurNode->ilink;
            }
            else
            {
                jpreNode->ilink = jcurNode->jlink;
            }
        }
        else
        {
            if (jcurNode->ivex == V2Add) {
                jpreNode->jlink = jcurNode->ilink;
            }
            else
            {
                jpreNode->jlink = jcurNode->jlink;
            }
        }
    }
    //4、删除目标结点
    free(icurNode); //free(jcurNode)，二选一
    return 1;
}

//输出邻接多重表中包含的所有边
void PrintEdges(AMLGraph* G) {
    int i;
    EBox* p = NULL;
    //重置所有结点的标志域
    InitMarks(G);
    for (i = 0; i < G->vexnum; i++) {
        p = G->adjmulist[i].firstedge;
        //如果当前结点存在，且标志域为 0
        while (p && (p->mark == 0)) {
            //输出该边，并将标志域置为 1
            printf("%c-%c ", G->adjmulist[p->ivex].data, G->adjmulist[p->jvex].data);
            p->mark = 1;
            if (p->ivex == i) {
                p = p->ilink;
            }
            else
            {
                p = p->jlink;
            }
        }
    }
    printf("\n");
}

//重置所有结点的标志域
void InitMarks(AMLGraph* G) {
    int i;
    EBox* p = NULL;
    for (i = 0; i < G->vexnum; i++) {
        p = G->adjmulist[i].firstedge;
        while (p && (p->mark == 1)) {
            p->mark = 0;
            if (p->ivex == i) {
                p = p->ilink;
            }
            else
            {
                p = p->jlink;
            }
        }
    }
}
//释放邻接多重表中申请的堆空间
//直接调用DeleteEdge()删除各个结点
Status DeleteDN(AMLGraph* G) {
    int i;
    EBox* p = NULL, * del = NULL;
    for (i = 0; i < G->vexnum; i++) {
        p = G->adjmulist[i].firstedge;
        while (p) {
            del = p;
            if (p->ivex == i) {
                p = p->ilink;
            }
            else
            {
                p = p->jlink;
            }
            DeleteEdge(G, G->adjmulist[del->ivex].data, G->adjmulist[del->jvex].data);
        }
    }
    return 1;
}
以图 1a) 中的无向图为例，用 A~E 表示 V1~V5，程序的执行结果为：

5 6
A B C D E
A B
A D
B C
C D
C E
B E5 6
A-D A-B B-E B-C C-E C-D
删除 A-B 边：
A-D B-E B-C C-E C-D


声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。
图的十字链表存储结构 深度优先搜索（DFS）算法
上一节 下一节

添加微信咨询 加站长微信免费领
C语言学习小册 加站长微信免费领C语言学习小册
微信ID：xiexuewu333