图的存储结构（邻接矩阵、邻接表、十字链表、邻接多重表）详解
上篇博客讲到，图状结构是非常复杂的结构，图也是非常复杂的，所以图的存储就是一个非常重要的部分，因为我们不仅要表示顶点集，还要表示边集，如何完整准确的表示图呢，接下来，给大家讲解四种图的存储方式。
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;