零、读前说明

• 本文中所有设计的代码均通过测试，并且在功能性方面均实现应有的功能。
• 设计的代码并非全部公开，部分无关紧要代码并没有贴出来。
• 如果你也对此感兴趣、也想测试源码的话，可以私聊我，非常欢迎一起探讨学习。
• 由于时间、水平、精力有限，文中难免会出现不准确、甚至错误的地方，也很欢迎大佬看见的话批评指正。
• 嘻嘻。。。。 。。。。。。。。收！
    
     这一篇因项目上线中间忙拖了很久了才发出来，虽说也不是很复杂的内容，但是在学习的过程总结还是有很缓慢的，不过万幸坚持做完了，累并快乐着！ 下一篇就不知道何年月能更新了（虽然看的人很少，但是还是要坚持做完），有事情回家一段时间，但愿所有事情能够顺利完成！！！

一、概 述

  在图中任何两个顶点之间都可能存在联系，所以图的存储结构应该需要根据具体问题的要求来进行设计。从图的逻辑结构定义来看，图中任何一个顶点都可以看成是第一个顶点。常用的存储结构有邻接矩阵、邻接表（逆邻接表）、十字链表、邻接多重表、 边集数组。那么本博文将带你就 “邻接表（逆邻接表）” 来窥探一二。。。

二、邻接表说明

  我们已经说明，对于稀疏图（边比较少的的图），邻接矩阵 占用空间大，空间浪费严重 。我们已经知道，使用链表形式可以明显的降低空间的浪费，那么是否可以将前面的数组形式的 邻接矩阵 用链表来表示呢。那么下面我们来看图的另外一种存储结构 — 邻接表 （Adjacency List） 。

  对于图中每个 顶点 $v_i$，将所有与 $v_i$ 邻接的 顶点 连成一个 单链表，称为顶点 $v_i$ 的 边表（对于有向图则分别称为 出边表，反之为 入边表）。

  也就是说：

  1、将图中 所有的顶点 用一个数组来存储（也可以使用单链表存储，但数组容易读取顶点信息， vertex ），同时还需要保存指向此顶点的第一个邻接点信息的指针（ firstEdge ），方便查找邻接点的信息；
  2、图中每一个顶点 $v_i$ 的所有邻接点组成一个 线性表，由于邻接点的个数不确定，所以选择用单链表来存储；
  像这样把 数组 与 链表 相结合的存储方式成为 邻接表。

  邻接表 有两种结构：顶点表节点 和 边表节点

  顶点表节点主要用于表示顶点的信息，主要需要记录顶点的信息、指向此顶点的顶一个邻接点的指针，同样可以添加其他需要的元素，比如节点的个数等。

  边表节点主要用于表示顶点的邻接点，以及下一个邻接点。当然同样可以添加其他的需要的元素，比如边的权值等。

  本博文中所使用的边表结构和顶点表结构如下图所示。

2.1、无向图的邻接表

  首先创造一个数组用来保存顶点的信息，以及一个指针指向顶点的第一个邻接点的指针，那么这个 first 指针域则成为了边表的头指针了。

  边表中的节点：表示的是节点在数组中的下标

  对于边 $(v_0,v_1)$ 在邻接表中，可以理解为：顶点表中的第 0 个顶点（$v_0$）到第 1 个顶点（$v_1$）有一条边。

  无向图邻接表如下图所示。

  顶点的度：与顶点 $v_i$ 连接的边的个数，也就是在 firstEdge 链表的节点的个数。

  如何去判断两个顶点 i, j 是否存在边：测试顶点 i 的边表中是否存在终点为 j 的节点。

2.2、有向图的邻接表

  有向图的邻接表是将顶点当作弧尾（默认是以弧尾）建立的邻接表，这样很容易的得到每个顶点的出度：顶点 i 的出边表的节点的个数。

  但是求入度则变得困难：依次查找各个顶点的出边表中以顶点 $v_i$ 为终点的节点的个数，所以需要将所有顶点及其边表扫描一遍。

  顶点 $v_i$ 的所有的邻接点：该边表中所有顶点都是顶点 $v_i$ 的邻接点。

  有向图邻接表如下图所示。

2.3、代码实现

2.3.1、数据类型及操作函数定义

  一、数据类型定义

  根据图的定义，定义图的数据结构类型中，需要包含两个重要的信息，一为 顶点的集合，二为 边的集合，本测试中加入一个 顶点的个数 的元素。测试代码中定义图的数据结构如下所示。

typedef void LGraph;
typedef void LVertex;

typedef struct _tag_LGraph
{
    int count;        // 顶点的个数
    LVertex **vertex; // 顶点的信息
    LinkList **first; // 边集
} TLGraph;

typedef struct _tag_ListNode
{
    LinkListNode next; //指向下一个边的指针
    int adjvex;        // 边的另一个顶点的下标
    int weight;        // 权值
} TListNode;

  二、图的操作函数定义

  图的操作，本博文中主要涉及三部分，创建销毁等操作、边的集合的操作、顶点的集合的操作。为了方便后续的添加其他的操作等，定义如下面代码所示。

#define UNDIRECTED_GRAPH 0               // 无向图定义
#define DIRECTED_GRAPH !UNDIRECTED_GRAPH // 有向图定义

/***
 *  边的操作集合
 **/
typedef struct __func_Edge
{
    int (*add)(LGraph *, int, int, int, int);
    int (*remove)(LGraph *, int, int, int);
    int (*get)(LGraph *, int, int);
    int (*count)(LGraph *, int);
} funcEdge;

/***
 *  顶点的操作集合
 **/
typedef struct __func_vertex
{
    int (*dgree)(LGraph *, int, int);
    int (*count)(LGraph *);
} funcVertex;

/***
 *  图的操作集合
 **/
typedef struct __func_Graph
{
    LGraph *(*create)(LVertex **, int);
    void (*destroy)(LGraph *);
    void (*clear)(LGraph *);
    void (*display)(LGraph *, int);
    funcEdge edge;     // 边的集合
    funcVertex vertex; //顶点的集合
} funcGraph;

extern funcGraph funGraph;

2.3.2、主要操作函数的代码实现

  图的操作主要实现代码，方便起见，文件名称类型为 .cpp ，注释比较详细，此处不在赘述，代码如下所示。

/**
 * 功 能：
 *      创建并返回有n个顶点的图
 * 参 数：
 *      v：与顶点相关的数据的指针
 *      n：顶点的个数
 * 返回值：
 *      成功：
 *      失败：NULL
 **/
LGraph *LGraph_Create(LVertex **v, int n) // O(n)
{
    TLGraph *ret = NULL;

    if ((v == NULL) || (n < 1))
        goto END;

    // 申请一个图结构内存
    ret = (TLGraph *)malloc(sizeof(TLGraph));
    if (ret == NULL)
        goto END;

    ret->count = n;                                          //  图的节点个数赋值
    ret->vertex = (LVertex **)calloc(n, sizeof(LVertex *));  // 申请节点的空间
    ret->first = (LinkList **)calloc(n, sizeof(LinkList *)); // 申请节点的邻接表的内存

    if ((ret->vertex == NULL) || (ret->first == NULL))
    {
        free(ret);
        free(ret->vertex);
        free(ret->first);
        ret = NULL;
        goto END;
    }

    // 顶点赋值
    for (int i = 0; i < n; i++)
    {
        ret->vertex[i] = v[i];
    }

    // 边集创建并赋值
    for (int i = 0; (i < n); i++)
    {
        // 创建链表
        ret->first[i] = funLinkList.create();
        if (ret->first[i] == NULL) // 创建失败
        {
            for (int j = 0; j < i; j++)
            {
                funLinkList.destory(ret->first[j]); // 销毁链表
            }
            // 内存释放
            free(ret->first);
            free(ret->vertex);
            free(ret);
            ret = NULL; // 返回值重定向
            break;
        }
    }

END:
    return ret;
}

/**
 * 功 能：
 *      添加顶点与顶点的关系 - 边
 *      在graph所指图中的v1和v2之间加上边，且边的权为w
 * 参 数：
 *      graph：要操作的图
 *      v1   ：顶点（尾）的编号（位置）
 *      v2   ：顶点（头）的编号（位置）
 *      w    ：权值，如果为0，表示边不存在
 *      flag ：表示是无向图还是有向图，如果为非0，表示为有向图
 * 返回值：
 *      0 ：添加成功
 *      -1：添加失败，参数异常
 **/
int LGraph_AddEdge(LGraph *graph, int v1, int v2, int w, int flag) // O(1)
{
    TLGraph *tGraph = (TLGraph *)graph;
    TListNode *node = NULL, *node1 = NULL;
    int ret = -1;

    if (graph == NULL || w < 0 || //  w即可表示存在边（=1）也可表示边的权值（>=1），在表示边的权值的时候，一定是边存在（>0）
        ((v1 < 0) && (v1 >= tGraph->count)) ||
        ((v2 < 0) && (v2 >= tGraph->count)))
        goto RET;

    node = (TListNode *)malloc(sizeof(TListNode));
    if (node == NULL)
        goto RET;

    node->adjvex = v2;
    node->weight = w;
    funLinkList.insert(tGraph->first[v1], (LinkListNode *)node,
                       funLinkList.length(tGraph->first[v1])); // 采用尾插入，方便在打印的时候比较

    if (!flag) // 如果是无向边，则再进行一次反向插入
    {
        node1 = (TListNode *)malloc(sizeof(TListNode));
        if (node == NULL)
            goto RET;

        node1->adjvex = v1;
        node1->weight = w;
        funLinkList.insert(tGraph->first[v2], (LinkListNode *)node1,
                           funLinkList.length(tGraph->first[v2])); // 采用尾插入，方便在打印的时候比较
    }
    ret = 0;
RET:
    return ret;
}

/**
 * 功 能：
 *      将graph所指图中v1和v2之间的边删除，返回权值
 * 参 数：
 *      graph：要操作的图
 *      v1   ：顶点（尾）的位置（编号）
 *      v2   ：顶点（头）的位置（编号）
 *      flag ：表示是无向图还是有向图，如果为非0，表示为有向图
 * 返回值：
 *      删除成功 ：非0值 -- 权值
 *      删除失败：0
 **/
int LGraph_RemoveEdge(LGraph *graph, int v1, int v2, int falg) // O(n*n)
{
    TLGraph *tGraph = (TLGraph *)graph;
    int ret = 0;
    TListNode *node = NULL;

    if ((tGraph == NULL) ||
        ((v1 < 0) && (v1 >= tGraph->count)) ||
        ((v2 < 0) && (v2 >= tGraph->count)))
        goto RET;

    for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++)
    {
        node = (TListNode *)funLinkList.get(tGraph->first[v1], i);
        if (node->adjvex == v2)
        {
            ret = node->weight;
            funLinkList.delet(tGraph->first[v1], i);
            break;
        }
    }
    if (!falg) // 如果是无线图的话，则删除反向的边
    {
        for (int i = 0; i < funLinkList.length(tGraph->first[v2]); i++)
        {
            node = (TListNode *)funLinkList.get(tGraph->first[v2], i);
            if (node->adjvex == v1)
            {
                funLinkList.delet(tGraph->first[v2], i);
                break;
            }
        }
    }

    free(node);
RET:
    return ret;
}

/**
 * 功 能：
 *      将graph所指图中v1和v2之间的边的权值返回
 * 参 数：
 *      graph：要操作的图
 *      v1   ：顶点（尾）的位置（编号）
 *      v2   ：顶点（头）的位置（编号）
 * 返回值：
 *      0  ：边 不存在
 *      -1 ：参数异常
 *      其他：边存在或者权值
 **/
int LGraph_GetEdge(LGraph *graph, int v1, int v2) // O(n*n)
{
    TLGraph *tGraph = (TLGraph *)graph;
    int ret = -1;
    TListNode *node = NULL;

    if ((tGraph == NULL) ||
        ((v1 < 0) && (v1 >= tGraph->count)) ||
        ((v2 < 0) && (v2 >= tGraph->count)))
        goto RET;

    for (int i = 0; i < funLinkList.length(tGraph->first[v1]); i++)
    {
        node = (TListNode *)funLinkList.get(tGraph->first[v1], i);
        if (node->adjvex == v2)
        {
            ret = node->weight;
            break;
        }
        else
            ret = 0;
    }

RET:
    return ret;
}
/**
 * 功 能：
 *      graph所指图中v顶点的度数
 * 参 数：
 *      graph：要操作的图
 *      v    ：顶点 的位置（编号）
 *      flag ：表示是无向图还是有向图，如果为非0，表示为有向图
 * 返回值：
 *      0  ：参数异常
 *      其他：顶点的度
 **/
int LGraph_VertexDgree(LGraph *graph, int v, int flag) // O(n*n*n)
{
    TLGraph *tGraph = (TLGraph *)graph;
    int ret = 0;

    if ((tGraph == NULL) ||
        ((v < 0) && (v >= tGraph->count)))
        goto RET;
    /**
     *  对于有向图 ，顶点的度为出度加上入度
     *      出度 ：等于邻接链表的长度
     *      入度 ：其他的在邻接链表中存在此节点的每一个顶点
     *  对于无线图，顶点的度等于邻接链表的长度
     **/
    // 此节点的邻接链表的长度
    ret += funLinkList.length(tGraph->first[v]);

    if (flag) // 如果是有向图，则需要判断其他顶点与此顶点的关系
    {
        // 遍历图中的每一个顶点
        for (int i = 0; i < tGraph->count; i++)
        {
            // 遍历顶点的邻接链表
            for (int j = 0; j < funLinkList.length(tGraph->first[i]); j++)
            {
                TListNode *node = (TListNode *)funLinkList.get(tGraph->first[i], j);
                if (node->adjvex == v) // 如果邻接链表中存在此节点
                    ret++;
            }
        }
    }
RET:

    return ret;
}

funcGraph funGraph = {
    LGraph_Create,
    LGraph_Destroy,
    LGraph_Clear,
    LGraph_Display_matrix,
    {
        LGraph_AddEdge,
        LGraph_RemoveEdge,
        LGraph_GetEdge,
        LGraph_EdgeCount,
    },
    {
        LGraph_VertexDgree,
        LGraph_VertexCount,
    }};

2.3.3、测试案例的实现源码

  主要进行相关代码的测试，方便起见，测试案例的名称为 main.cpp ，注释比较详细，此处不在赘述说明，代码如下所示。

#include "../src/graph/graph.h"
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    system("color "); // 颜色设置，用于在windows下终端显示的时候不明原因换行的问题

    printf("\n\e[1;31mLet's start with an example of an undirected graph:\e[0m\n");

    LVertex const *v[] = {"A", "B", "C", "D", "E", "F"};
    LGraph *ungraph = funGraph.create((LVertex **)v, 6);

    // 添加边
    funGraph.edge.add(ungraph, 0, 1, 1, UNDIRECTED_GRAPH); // (A, B)
    funGraph.edge.add(ungraph, 0, 2, 1, UNDIRECTED_GRAPH); // (A, C)
    funGraph.edge.add(ungraph, 0, 3, 1, UNDIRECTED_GRAPH); // (A, D)
    funGraph.edge.add(ungraph, 1, 4, 1, UNDIRECTED_GRAPH); // (B, E)
    funGraph.edge.add(ungraph, 1, 5, 1, UNDIRECTED_GRAPH); // (B, F)
    funGraph.edge.add(ungraph, 2, 1, 1, UNDIRECTED_GRAPH); // (C, B)
    funGraph.edge.add(ungraph, 3, 4, 1, UNDIRECTED_GRAPH); // (D, E)

    // 顶点的个数
    printf("\nThe number of vertices in the graph is : %d\n", funGraph.vertex.count(ungraph));

    // 显示邻接表
    printf("\nThe Adjacency List of the graph is :\n");
    funGraph.display(ungraph, 1);

    // 边的个数
    printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));
    // 顶点的度，参数为顶点在数组的下标
    printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));

    // 添加边，带有权值
    funGraph.edge.add(ungraph, 4, 2, 9, UNDIRECTED_GRAPH); // (E, C)  9

    // 边的权值
    printf("\nThe Weight of Edge (E, C) is : %d\n", funGraph.edge.get(ungraph, 4, 2));

    printf("\nThe Adjacency List of the graph is :\n");
    funGraph.display(ungraph, 0);

    // 添加边，带有权值  （E, C)
    funGraph.edge.remove(ungraph, 4, 2, 0);

    // 显示邻接表
    printf("\nThe Adjacency List of the graph is :\n");
    funGraph.display(ungraph, 0);

    // 边的个数
    printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(ungraph, UNDIRECTED_GRAPH));
    // 顶点的度，参数为顶点在数组的下标
    printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(ungraph, 1, UNDIRECTED_GRAPH));
	// fixed 2020.08.29 : 原本测试时（下图中显示效果）写的是“undirected”，为错误的，现已经改正！
    printf("\n\e[1;31mLet's start with an example of directed graph:\e[0m\n");

    LGraph *graph = funGraph.create((LVertex **)v, 6);

    // 添加边
    funGraph.edge.add(graph, 0, 1, 1, DIRECTED_GRAPH); // <A, B>
    funGraph.edge.add(graph, 0, 2, 1, DIRECTED_GRAPH); // <A, C>
    funGraph.edge.add(graph, 0, 3, 1, DIRECTED_GRAPH); // <A, D>
    funGraph.edge.add(graph, 1, 4, 1, DIRECTED_GRAPH); // <B, E>
    funGraph.edge.add(graph, 1, 5, 1, DIRECTED_GRAPH); // <B, F>
    funGraph.edge.add(graph, 2, 1, 1, DIRECTED_GRAPH); // <C, B>
    funGraph.edge.add(graph, 3, 4, 8, DIRECTED_GRAPH); // <D, E>

    // 显示邻接表
    printf("\nThe Adjacency List of the graph is :\n");
    funGraph.display(graph, 0);

    // 边的个数
    printf("\nThe number of Edge in the graph is : %d\n", funGraph.edge.count(graph, DIRECTED_GRAPH));
    // 顶点的度，参数为顶点在数组的下标
    printf("\nThe Degree of vertex 'B' is : %d\n", funGraph.vertex.dgree(graph, 1, DIRECTED_GRAPH));
    // 权值
    printf("\nThe Weight of Edge <D, E> is : %d\n", funGraph.edge.get(graph, 3, 4));

    funGraph.destroy(ungraph);
    funGraph.destroy(graph);

    printf("\n\e[1;32msystem exited with return code %d\e[0m\n\n", 0);

    return 0;
}

  方便后续的测试与对照，上面测试案例中创建的图的显示效果如下图所示。

2.4、测试效果

  本次测试是在 windows 环境下进行，也可以在 linux 环境下操作，详细说明在README.md中查看。

  使用 Cmake 编译，使用下面指令：

mkdir build ; cd build
在windows下使用    ： cmake -G "MinGW Makefiles" .. # 注意 .. ,表示上级目录
在linux下使用      ： cmake -G "Unix Makefiles" .. # 注意 .. ,表示上级目录
在linux下也可以使用 ： cmake .. # 注意 .. ,表示上级目录
make

  经过cmake编译之后，可以使用在当前目录下使用指令 ./../runtime/graph来运行可执行程序，也可以进入到目录runtime中，然后使用指令 ./graph ，即可运行测试程序。实际测试的结果如下图所示。

  
  至此，代码全部运行完成。

三、逆邻接表

  一、逆邻接表

  逆邻接表指的是将顶点当弧头建立的邻接表，这样便于得到每个顶点的 入度 或者以此顶点为弧头的弧。

  有向图邻接表如下图所示。

  二、带权值的图（网）

  前面已经提到了，对于带有权值的边，只需要在边表节点的定义在增加一个数据域来存储权值即可。

  带权值的图如下图所示。

四、简单对比总结

   比较邻接矩阵、邻接点表的有确定，如下表所示。

  好啦，废话不多说，总结写作不易，如果你喜欢这篇文章或者对你有用，请动动你发财的小手手帮忙点个赞，当然 关注一波 那就更好了，好啦，就到这儿了，么么哒(* ￣3)(ε￣ *)。

 

上一篇：数据结构（廿二） – C语言版 – 图 - 图的存储结构 – 邻接矩阵
下一篇：数据结构（廿四） – C语言版 – 图 - 图的存储结构 – 十字链表、邻接多重表、 边集数组

1.图的邻接表与逆邻接表直接看下图理解：

2.由邻接表导出逆邻接表代码：

void Reverse(ALGraph A,ALGraph &B)
{
    int i,k;
    ArcNode *p1,*p2;
    B.vn=A.vn;
    B.en=A.en;
    for(i=1; i<=A.vn; i++)
    {
        scanf("%c",&B.adjlist[i].data);
        B.adjlist[i].firstarc=NULL;
    }

    for(i=1; i<=A.vn; i++)
    {
        p1=A.adjlist[i].firstarc;
        while(p1)
        {
            k=p1->adjvex;
            p2=(ArcNode *)malloc(sizeof(ArcNode));
            p2->adjvex=i;
            p2->nextarc=B.adjlist[k].firstarc;
            B.adjlist[k].firstarc=p2;
            p1=p1->nextarc;
        }
    }
}

邻接表作为图的一种存储方式，在存储稀疏图上相对于邻接矩阵有相当大的空间节省。如一个稀疏图的顶点个个数为n，边数为e。用邻接矩阵存储需要n^2空间，而真正进行存储的只有2e个空间， 剩下的n^2-2e都浪费了。但是对于邻接表来讲，存储空间只需要n+2e个，相对于邻接矩阵减少了很多。邻接表虽然在空间上有很大的优势，但是对于一个有向图，如果需要查找每个顶点的入度就需要遍历整个邻接表，在效率上很低下的。因此才有了逆邻接表的诞生。

邻接表：反映的是顶点出度的情况。
逆邻接表：反映的是顶点的入度情况。

下面举一个例子：

邻接表：

逆邻接表：