【数据结构必备基本知识】图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）详解

缺乏、安全感 2021-06-11 15:13 640阅读 0赞

上篇博客讲到，图状结构是非常复杂的结构，图也是非常复杂的，所以图的存储就是一个非常重要的部分，因为我们不仅要表示顶点集，还要表示边集，如何完整准确的表示图呢，接下来，给大家讲解四种图的存储方式。

# 一、邻接矩阵法 #

## 1、定义 ##

我们用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

设G=(V,E)是一个图，其中V=\{v1,v2,…,vn\}，若(Vi,Vj)∈E，则A\[ i，j \] = 1，否则A\[ i，j \] = 0；即下图

![20181104221824946.png][]

对于带权图来说，可以将A\[ i，j \] 用来存储权值，如果两结点无连接，用无穷表示。

![20181104222040549.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70][] 带权图示例

## 2、特点 ##

无向图的邻接矩阵对称且唯一。

有向图的邻接矩阵的第 i 行非零元素个数为第 i 个顶点的出度；第 j 列非零元素个数为第 j 个顶点的入度。

稠密图更适合用邻接矩阵存储。

## 3、代码 ##

#define MaxVertexNum 100  //Maximum value of the vertex number
    
    typedef char VertexType; //the type of vertex
    typedef int EdgeType; // the type of wight on the edge in weighted graph 带权图中边上的权值的类型
    
    
    // the graph are storaged by adjacency matrix 邻接矩阵存储图
    typedef struct {
    	VertexType Vex[MaxVertexNum];
    	EdgeType Edge[MaxVertexNum][MaxVertexNum];  // adjacency matrix
    	int vexNum, arcNum;  //current vertex number and arc of graph
    }MGraph;

# 二、邻接表法 #

## 1、定义 ##

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如下图是无向图的邻接表法表示

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1][]

## 2、特点 ##

邻接表法是为了节省存储空间引入的，对于稀疏图，相对于邻接矩阵，无需耗费大量存储空间，对于有向图来说，还有逆邻接表的概念，如下图，是有向图的邻接表，表中指向方向与图本身指向方向相同，所以有向图的邻接表可以得到图的出度，逆邻接表可以得到图的入度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2][]

## 3、代码 ##

#define MaxVertexNum 100  //Maximum value of the vertex number
    
    //the graph are storaged by adjacency list
    typedef struct ArcNode {
    	int adjvex;  // the location of the vertex which was pointed by arc
    	struct ArcNode *next;
    	
    }ArcNode;
    
    typedef struct VNode {
    	VertexType data;
    	ArcNode *first;
    }VNode,AdjList[MaxVertexNum];
    
    typedef struct {
    	AdjList vertices;  // adjacency list
    	int vexNum, arcNum;  // current vertex number and arc of graph
    }ALGraph;

# 三、十字链表 #

## 1、定义 ##

十字链表（Orthogonal List)是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。同时，代码的可读性也会得到提升。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3][] 有向图的十字链表表示

## 2、特点 ##

十字链表容易找到vi为尾的弧，也容易找到vi为头的弧，因而容易求得顶点的入度与出度。

**图的十字链表表示不唯一，但一个十字链表表示一个确定的图**。

## 3、代码 ##

#define MaxVertexNum 100  //Maximum value of the vertex number
    
    // the graph are storaged by orthogonal list
    typedef struct ArcNode {
    	int tailvex, headvex;  // the location of the vertex which was pointed by arc
    	struct ArcNode *hlink, *tlink;
    
    }ArcNode;
    
    typedef struct VNode {
    	VertexType data;
    	ArcNode *firstIn, *firshOut;
    }VNode;
    
    typedef struct {
    	VNode xList[MaxVertexNum];  // adjacency list
    	int vexNum, arcNum;  // current vertex number and arc of graph
    }GLGraph;

# 四、邻接多重表 #

## 1、引入 ##

十字链表是对有向图的存储结构进行另一个角度的表示，同样的邻接多重表是对无向图的另一种表示方法。

如果我们在无向图的应用中，更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。

## 2、特点 ##

在邻接多重表中，每一条边用一个结点来表示，结构如下：

![20181104225103206.png][]

其中，mark为标志域，用于标记该条边是否被访问；ivex与jvex为该条边的两个顶点的位置；ilink为指向下一条依附于顶点ivex的边，jlink为指向下一条依附于顶点jvex的边；info为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，该结点由如下两个域组成：

![20181104225544947.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 4][] 无向图的邻接多重表表示

##  3、代码 ##

#define MaxVertexNum 100  //Maximum value of the vertex number
    
    
    // the graph are storaged by adjacency multiple tables
    typedef struct ArcNode {
    	bool mark;
    	int ivex, jvex;  
    	struct ArcNode *ilink, *jlink;
    
    }ArcNode;
    
    typedef struct VNode {
    	VertexType data;
    	ArcNode *firstedgr;
    }VNode;
    
    typedef struct {
    	VNode agjmuList[MaxVertexNum];  
    	int vexNum, arcNum;  
    }AMLGraph;

[20181104221824946.png]: /images/20210516/054374b4a975473c8071afca4253d60a.png
[20181104222040549.png]: /images/20210516/3055015b531145a7b1fdbf596b9f9cd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70]: /images/20210516/7b063fcc27c144b7b6a59d269d09df1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 1]: /images/20210516/5b9c1ee48cdc43e2920240e71e3d82df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 2]: /images/20210516/d556d8445a3248109abffd29fd7bc578.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 3]: /images/20210516/f901f2e784d9421ebc27fba0677bb397.png
[20181104225103206.png]: /images/20210516/a9488e1ea62841308d5453a879082726.png
[20181104225544947.png]: /images/20210516/9ffc4c3564db4a94991e7e959ca9233e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_16_color_FFFFFF_t_70 4]: /images/20210516/525922b71bb74d108e33e80137160910.png