数据结构之图的存储方式

数据结构与算法

---

二、图的抽象数据类型

ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G):       图G存在则销毁。
    LocateVex(G, u):        若图G中存在顶点u，则返回图中的位置。
    GetVex(G, v):           返回图G中顶点v的值。
    PutVex(G, v, value):    将图G中顶点v赋值value。
    FirstAdjVex(G, *v):     返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex(G, v, *w):   返回顶点v相对于顶点w的下一个邻接顶点，
                            若w是v的最后一个邻接点则返回“空”。
    InsertVex(*G, v):       在图G中增添新顶点v。
    DeleteVex(*G, v):       删除图G中顶点v及其相关的弧。
    InsertArc(*G, v, w):    在图G中增添弧<v,w>，若G是无向图，还需要增添对称弧<w,v>。
    DeleteArc(*G, v, w):    在图G中删除弧<v,w>，若G是无向图，则还删除对称弧<w,v>。
    DFSTraverse(G):         对图G中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G):         对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

三、图的存储结构

3.1 邻接矩阵

图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。

考虑到图是由顶点和边或弧两部分组成。合在一起比较困难，那就很自然地考虑到分两个结构来分别存储。顶点不分大小、主次，所以用一个一维数组来存储是很不错的选择。而边或弧由于是顶点与顶点之间的关系，一维搞不定，那就考虑用一个二维数组来存储。这就诞生了邻接矩阵。

设图G有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：

$$arc[i][j] = \begin{cases} 1, & \text{若（vi,vj）∈E或<vi,vj>}∈E \\ 0, & \text{反之} \end{cases} \\ \\ $$
无向图的邻接矩阵：

$对于矩阵的主对角线的值，即arc[0][0]、arc[1][6]、arc[2][7]、arc[3][8]，全为0是因为不存在顶点到自身\\的边，比如v_0到v_0。arc[0][9]=1是因为v_0到v_1的边存在，而arc[1][10]=0是因为v_1到v_3的边不存在。并且由于\\是无向图，v_1到v_3的边不存在，意味着v_3到v_1的边也不存在。所以无向图的边数组是一个对称矩阵。$

根据这个矩阵， 可以知道很多信息：

• 要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行（或第i列）的元素之和。比如顶点v1的度就是1+0+1+0=2。
• 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

有向图的邻接矩阵：

但因为是有向图，所以此矩阵并不对称，比如由v1到v0有弧，得到$arc[1][0]=1$，而v0到v1没有弧，因此$arc[0][12]=0$。
有向图讲究入度与出度，顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。
与无向图同样的办法，判断顶点vi到vj是否存在弧，只需要查找矩阵中$arc[i][j]$是否为1即可。要求vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找$arc[i][j]$为1的顶点。

网的邻接矩阵：
设图G是网图，有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
这里$w_{ij}$表示$（v_i,v_j）$或$<v_i,v_j>$上的权值。∞表示一个计算机允许的、大于所有边上权值的值，也就是一个不可能的极限值。不为0的原因在于权值$w_{ij}$大多数情况下是正值，但个别时候可能就是0，甚至有可能是负值。因此必须要用一个不可能的值来代表不存在。下就是一个有向网图，右图就是它的邻接矩阵。

/* 顶点类型应由用户定义 */
typedef char VertexType;             
/* 边上的权值类型应由用户定义 */
typedef int EdgeType;                
/* 最大顶点数，应由用户定义 */
#define MAXVEX 100                   
/* 用65535来代表∞ */
#define INFINITY 65535               
typedef struct
{
    /* 顶点表 */
    VertexType vexs[MAXVEX];         
    /* 邻接矩阵，可看作边表 */
    EdgeType arc[MAXVEX][MAXVEX];    
    /* 图中当前的顶点数和边数 */
    int numVertexes, numEdges;       
} MGraph;

无向网图的创建代码：

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    /* 输入顶点数和边数 */
    scanf("%d,%d", &G->numVertexes, &G->numEdges);    
    /* 读入顶点信息，建立顶点表 */
    for (i = 0; i < G->numVertexes; i++)              
        scanf(&G->vexs[i]);
    for (i = 0; i < G->numVertexes; i++)
        for (j = 0; j <G->numVertexes; j++)
            /* 邻接矩阵初始化 */
            G->arc[i][j] = INFINITY;                  
    /* 读入numEdges条边，建立邻接矩阵 */
    for (k = 0; k < G->numEdges; k++)                 
    {
        printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
        /* 输入边(vi,vj)上的权w */
        scanf("%d,%d,%d", &i, &j, &w);                
        G->arc[i][j] = w;
        /* 因为是无向图，矩阵对称 */
        G->arc[j][i] = G->arc[i][j];                  
    }
}

从代码中也可以得到，n个顶点和e条边的无向网图的创建，时间复杂度为$O(n+n^2+e)$，其中对邻接矩阵G.arc的初始化耗费了$O(n^2)$的时间。

3.2 邻接表

邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。

使用数组与链表相结合的存储方式，就诞生了邻接表（Ad-jacency List）。

邻接表的处理办法是这样:
1. 图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
2. 图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2。

有向图的邻接表：

有向图由于有方向，以顶点为弧尾来存储边表，这样就很容易就可以得到每个顶点的出度。但也有时为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表，即对每个顶点vi都建立一个链接为vi为弧头的表。如上图的第三幅图所示。

网图的邻接表
对于带权值的网图，可以在边表结点定义中再增加一个weight的数据域，存储权值信息即可，如下图：

/* 顶点类型应由用户定义 */
typedef char VertexType;          
/* 边上的权值类型应由用户定义 */
typedef int EdgeType;             
/* 边表结点 */
typedef struct EdgeNode           
{
    /* 邻接点域，存储该顶点对应的下标 */
    int adjvex;                   
    /* 用于存储权值，对于非网图可以不需要 */
    EdgeType weight;              
    /* 链域，指向下一个邻接点　 */
    struct EdgeNode *next;        
} EdgeNode;
/* 顶点表结点 */
typedef struct VertexNode         
{
    /* 顶点域，存储顶点信息 */
    VertexType data;              
    /* 边表头指针 */
    EdgeNode *firstedge;          
} VertexNode, AdjList[MAXVEX];
typedef struct
{
    AdjList adjList;
    /* 图中当前顶点数和边数 */
    int numVertexes, numEdges;    
} GraphAdjList;

无向图的邻接表创建代码如下:

/* 建立图的邻接表结构 */
void  CreateALGraph(GraphAdjList *G)
{
    int i, j, k;
    EdgeNode *e;
    printf("输入顶点数和边数:\n");
    /* 输入顶点数和边数 */
    scanf("%d,%d", &G->numVertexes, 
          &G->numEdges);    
    /* 读入顶点信息，建立顶点表 */
    for (i = 0; i < G->numVertexes; i++)              
    {
        /* 输入顶点信息 */
        scanf(&G->adjList[i].data);                   
        /* 将边表置为空表 */
        G->adjList[i].firstedge = NULL;               
    }
    /* 建立边表 */
    for (k = 0; k < G->numEdges; k++)                 
    {
        printf("输入边(vi,vj)上的顶点序号:\n");
        /* 输入边(vi,vj)上的顶点序号 */
        scanf("%d,%d", &i, &j);                       
        /* 向内存申请空间， */
        /* 生成边表结点 */
        e = (EdgeNode *)malloc(sizeof(EdgeNode));     
        /* 邻接序号为j */
        e->adjvex = j;                                
        /* 将e指针指向当前顶点指向的结点 */
        e->next = G->adjList[i].firstedge;            
        /* 将当前顶点的指针指向e */
        G->adjList[i].firstedge = e;                  
        /* 向内存申请空间， */
        /* 生成边表结点 */
        e = (EdgeNode *)malloc(sizeof(EdgeNode));     
        /* 邻接序号为i */
        e->adjvex = i;                                
        /* 将e指针指向当前顶点指向的结点 */
        e->next = G->adjList[j].firstedge;            
        /* 将当前顶点的指针指向e */
        G->adjList[j].firstedge = e;                  
    }
}

本算法的时间复杂度，对于n个顶点e条边来说，很容易得出是O(n+e)。

3.3 十字链表

那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。

把邻接表与逆邻接表结合起来，这就是十字链表（Orthogonal List）。

顶点表结点结构：data —— firstin(入边表头指针) —— firstout(出边表头指针)
边表结点结构：

其中tailvex是指弧起点在顶点表的下标，headvex是指弧终点在顶点表中的下标，headlink是指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，还可以再增加一个weight域来存储权值。

如下图：

虚线箭头其实就是此图的逆邻接表的表示。对于v0来说，它有两个顶点v1和v2的入边。因此v0的firstin指向顶点v1的边表结点中headvex为0的结点，如上图中的①。接着由入边结点的headlink指向下一个入边顶点v2，如图中的②。对于顶点v1，它有一个入边顶点v2，所以它的firstin指向顶点v2的边表结点中headvex为1的结点，如图中的③。顶点v2和v3也是同样有一个入边顶点，如图中④和⑤。

十字链表的好处就是因为把邻接表和逆邻接表整合在了一起，这样既容易找到以vi为尾的弧，也容易找到以vi为头的弧，因而容易求得顶点的出度和入度。而且它除了结构复杂一点外，其实创建图算法的时间复杂度是和邻接表相同的，因此，在有向图的应用中，十字链表是非常好的数据结构模型。

3.4 邻接多重表

如果在无向图的应用中，关注的重点是顶点，那么邻接表是不错的选择，但如果更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，却是比较繁琐的。因此可以仿照十字链表的方式，对边表结点的结构进行一些改造。
重新定义的边表结点结构：

其中ivex和jvex是与某条边依附的两个顶点在顶点表中的下标。ilink指向依附顶点ivex的下一条边，jlink指向依附顶点jvex的下一条边。这就是邻接多重表结构。

邻接多重表构造过程
① 先把顶点与边表节点画出；如下图，由于是无向图，所以ivex是0、jvex是1还是反过来都是无所谓的，不过为了绘图方便，都将ivex值设置得与一旁的顶点下标相同。

② 开始连线，首先连线的①②③④就是将顶点的firstedge指向一条边，顶点下标要与ivex的值相同；

③ 接着，由于顶点v0的(v0,v1)边的邻边有(v0,v3)和(v0,v2)。因此⑤⑥的连线就是满足指向下一条依附于顶点v0的边的目标，注意ilink指向的结点的jvex一定要和它本身的ivex的值相同。
④ 同样的道理，连线⑦就是指(v1,v0)这条边，它是相当于顶点v1指向(v1,v2)边后的下一条。v2有三条边依附，所以在③之后就有了⑧⑨。连线⑩的就是顶点v3在连线④之后的下一条边。
左图一共有5条边，所以右图有10条连线，完全符合预期。

邻接多重表与邻接表的差别，仅仅是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。这样对边的操作就方便多了，若要删除左图的(v0,v2)这条边，只需要将右图的⑥⑨的链接指向改为∧即可。

3.5 边集数组

边集数组是由两个一维数组构成。一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成，如下图：

边集数组关注的是边的集合，在边集数组中要查找一个顶点的度需要扫描整个边数组，效率并不高。因此它更适合对边依次进行处理的操作，而不适合对顶点相关的操作。