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

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

一、邻接矩阵法

1、定义

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

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

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

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、定义

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

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

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、特点

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

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

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

 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;