本文共 5646 字，大约阅读时间需要 18 分钟。

图的表示

那如何在内存中存储一个图呢？

图在内存中的存储方式有很多种，包括邻接矩阵、邻接表、逆邻接表、十字链表等

邻接矩阵

拥有n个顶点的图，它所包含的连接数量最多是n(n-1)个。因此，要表达各个顶点之间的关联关系，最清晰易懂的方式是使用二维数组(矩阵)。

我们先来看无向图的矩阵表示：

如图所示，

• 顶点0和顶点1之间有边关联，那么矩阵中的元素A[0][1]与A[1][0]的值就是1
• 顶点1和顶点2之间没有边关联，那么矩阵中的元素A[1][2]与A[2][1]的值就是0

像这样表达图种顶点关联关系的矩阵，就叫做邻接矩阵。

需要注意的是

• 矩阵从左上到右下的一条对角线，其上的元素值必然是0，因为任何一个顶点与它子树是没有连接的。
• 同时，无向图对应的矩阵是一个对称矩阵，V0和VV1有关联，那么V1和V0也必定有关联，因此A[0][1]和A[1][0]的值一定相等

那么，有向图的邻接矩阵又是什么样子呢？

从图中可以看出：

• 有向图不再是一个对称矩阵。从V0可以到底V1，从V1却未必能到底V0，因此A[0][1]和A[1][0]的值不一定相等。

邻接矩阵的优点：简单直观，可以快速查到一个顶点和另一个顶点之间的关系

邻接矩阵的缺点：占用了太多空间。比如，如果一个图有1000个顶点，其中只有10个顶点之间有关联(这种情况叫做稀疏图)，却不得不建立一个1000*1000的二维数组，太浪费了

邻接表和逆邻接表

为了解决邻接矩阵占用空间的问题，于是邻接表出现了。

在邻接表中，图中的每一个顶点都是链接的头节点，其后连接这该顶点能够直接达到的相邻顶点。

很明显，这种邻接表的存储方式，占用的空间比邻接矩阵要小很多。

要想查出从顶点0能否到达顶点1，该怎么做呢？很简单，我们从顶点0开始，顺着链表的头节点从后遍历，看看后继的节点中是否存在顶点1.

要想查出顶点0能够到达的所有相邻节点，也很简单，从顶点0向后的所有链表节点，就是顶点0能够到达的相邻节点。

那么，要想查出有哪些节点能一步到达顶点1，又该怎么做呢？这样就麻烦一些了，我们要遍历每一个顶点所在的链表，看看链表节点中是否包含节点1，最后发现顶点0和顶点3可以到达顶点1。

像这种逆向查找的麻烦，该如何解决呢？我们可以是用逆邻接表来解决。

逆邻接表顾名思义，和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点，后继节点所存储的是能够直接达到该顶点的相邻顶点。

这样一来，要想查出有哪些节点能一步到达顶点1就容易了，从顶点1向后的所有链表节点，就是能一步到达顶点1的节点。

因此，我们可以根据实际需求，选择使用邻接表还是逆邻接表。

问题是，一个图总是要维护正反两个邻接表，也太麻烦了。这时就出现了把邻接表和逆邻接表结合在一起的十字链表

十字链表

十字链表长什么样呢？用最直观的示意，是下面这样：

如图所示，十字链表的每一个顶点，都是两个链表的根节点，其中一个链表存储着该顶点能到达的相邻顶点，另一个链表存储着能到达该顶点的相邻节点。

不过，上图只是一个便于理解的示意图，我们没有必要把链表的节点都重复存储两次。在优化之后的十字链表中，链表的每一个节点不再是顶点，而是一条边，里面包含起止顶点的下标。

十字链表节点和边的对应关系，如下图所示：

因此，优化之后的十字链表，是下面这个样子：

图中每一条带有蓝色箭头的链表，存储着从顶点出发的边；每一条带有橙色箭头的链表，存储着进入顶点的边

看个例子

利用两个数组分布存储顶点和边。

邻接矩阵

（1）我们先只考虑图顶点的信息：先用一个一维数组存储图的顶点。

对于G1，它的顶点用数组存储

对于G2，它的顶点用数组存储

（2）我们再来考虑图的边。因为一条边连接两个顶点，为了描述这个关系，再利用一个二维数组来存储图的边。把二维数组看成是一个矩阵。

对于G1，它的边用二维数组

其中E[i][j]为1表示，从顶点v[i]到顶点v[j]有边（这是有方向的）

对于无向图G2,它的边也可以用二维数组来表示：

其中E[i][j]为1表示顶点V[i]与V[j]之间有边（没有方向），注意：这和有向图是不一样的，大家可以看到无向图的二维数组是关于对角线对称的。

这样通过一维数组来保存顶点数据信息，二维数组来表示两两顶点的边。就完成了对图形数据结构的存储

下面是一个无向图的实现：

/*GraphStruct.h* 图的邻接矩阵存储方式，结构由顶点数量、边数量、顶点集合和边集合组成。* 其中顶点集合一维数组，根据顶点的数量动态分配数组大小。* 边集合是二维数组，根据顶点的数量来动态分配数组大小，对于无向图来说，该邻接矩阵是对称矩阵。* 邻接矩阵比较适用于稠密图*/typedef char vertexType;typedef int edgeType;typedef struct GraphMatrix{
       int vertexNumber;            // 顶点数量    int edgeNumber;                // 边的数量    vertexType *vertex;            // 顶点集合，动态数组    edgeType** edge;            // 边集合，二维动态数组} GraphMatrix;void GraphMatrix_create(GraphMatrix *g);

#include 
   
     #include 
    
     #include"GraphStruct.h"void GraphMatrix_create(GraphMatrix *g){
       printf("请分别输入图的顶点数量和边的数量，用空格隔开：");    scanf("%d %d", &g->vertexNumber, &g->edgeNumber);    g->vertex = (vertexType *)malloc(g->vertexNumber * sizeof(vertexType)); //为动态数组申请空间    //二维动态数组申请空间    g->edge =(edgeType**)malloc(g->vertexNumber * sizeof(edgeType*));    for (int i = 0; i < g->vertexNumber; i++){
           g->edge[i] = (edgeType*)malloc(g->vertexNumber * sizeof(edgeType));    }    //初始化邻接矩阵的所有元素    for (int i = 0; i < g->vertexNumber; ++i) {
           for (int j = 0; j < g->vertexNumber; ++j) {
               g->edge[i][j] = 0;        }    }        //输入图的信息    for (int k = 0; k < g->edgeNumber ; ++k) {
           int i, j;        printf("请输入边(vi,vj)的下标, i和j，用空格隔开:");        scanf("%d %d", &i, &j);        g->edge[i][j] = 1;        g->edge[j][i] = 1;    }    //输出图的信息    printf("Your graph matrix is :\n");    for (int i = 0; i < g->vertexNumber; i++){
           for (int j = 0; j < g->vertexNumber; j++){
               printf("%d\t", g->edge[i][j]);        }        printf("\n");    }}
    
   

int main(){
       GraphMatrix *gm;    gm = (GraphMatrix *)malloc(sizeof(GraphMatrix));    GraphMatrix_create(gm);    return 0;}

邻接表

（1）我们依然先利用一维数组将图的订单存储起来

对于G1

先强调一下弧头和弧尾以及弧的概念：弧头和弧尾都是指顶点，在G1中，对于Ea来说V1是弧头，V2是弧尾

（2）再将图的边加进来

综上，对于边(i,j)，邻接表如下：

左边的节点称为顶点节点，其结构体包含顶点元素和指向第一条边的指针；右边的为边节点，结构体包含边的顶点对应的下标，和指向下一个边节点的指针。对于有权值的网图，只需要在边节点增加一个权值的成员变量即可。

typedef char vertexType;typedef int edgeType;typedef struct ListEdgeNode{
       int index;                    // 边的下标    struct ListEdgeNode *next;            // 指向下一个节点的指针}ListEdgeNode;typedef struct ListVertexNode {
       vertexType vertex;            // 顶点    ListEdgeNode *fistEdge;        // 指向第一条边} ListVertexNode;// GraphList是链接表的结构体，包含了顶点数，边数和顶点集，其中顶点集根据顶点个数分配内存空间。typedef struct GraphList{
       int vertexNumber;            // 顶点的数量    int edgeNumber;                // 边的数量    ListVertexNode *vertex;        // 顶点集合，动态数组}GraphList;

void GraphList_Create(GraphList *g){
       printf("请分别输入图的顶点数量和边的数量，用空格隔开：");    scanf("%d %d", &g->vertexNumber, &g->edgeNumber);    //为动态数组申请空间    g->vertex = (ListVertexNode *)malloc(g->vertexNumber * sizeof(ListVertexNode));    //初始化顶点指的第一条边    for (int i = 0; i < g->edgeNumber; ++i) {
           g->vertex[i].fistEdge = NULL;    }    //输入图的信息    ListEdgeNode *listEdgeNode;    for (int j = 0; j < g->edgeNumber; ++j) {
           int i, v;        printf("请输入边(vi,vj)的下标, i和j，用空格隔开:");        scanf("%d%d", &i, &j);        //始终将插入的节点放在顶点所指的一条边        listEdgeNode = (ListEdgeNode *)malloc(sizeof(ListEdgeNode));        listEdgeNode->index = j;        listEdgeNode->next = g->vertex[i].fistEdge;        g->vertex[i].fistEdge = listEdgeNode;        listEdgeNode = (ListEdgeNode*)malloc(sizeof(ListEdgeNode));        listEdgeNode->index = i;        listEdgeNode->next = g->vertex[j].fistEdge;        g->vertex[j].fistEdge = listEdgeNode;    }    //输出图的信息    ListEdgeNode * node = NULL;    for (int i = 0; i < g->vertexNumber; ++i) {
           if (g->vertex[i].fistEdge != NULL){
               node = g->vertex[i].fistEdge;        }        while (node != NULL){
               printf("%d --- %d\t", i, node->index);            node = node->next;        }        printf("\n");    }}

int main(){
       GraphList *gl;    gl = (GraphList*)malloc(sizeof(GraphList));    GraphList_Create(gl);    return 0;}

转载地址：https://blog.csdn.net/zhizhengguan/article/details/122457235 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！