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

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

一、邻接矩阵法

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 numbertypedef char VertexType; //the type of vertextypedef 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 listtypedef 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 listtypedef 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 tablestypedef 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;

转载地址：http://qdyni.baihongyu.com/