邻接矩阵(无向图)
考虑到图是由顶点和边或弧两部分组成,合在一起比较困难，那就很自然地考虑到分为两个结构来分别存储。
顶点因为不区分大小、主次，所以用一个一维数组来存储是狠不错的选择。

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

 我们可以设置两个数组，顶点数组为
vertex[4]={vO,v1,V2,V3}，边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边，1表示顶点间存在边)。
对称矩阵:所谓对称矩阵就是n阶矩阵的元满足a[i][j]=a[j][i](0<=i,j<=n)。即从矩阵的左上角到右下角的主对角线为轴，右上角的元与左下角相对应的元全都是相等的。

无向图的边构成了一个对称矩阵，貌似浪费了一半的空间，那如果是有向图来存放,会不会把资源都利用得很好呢?

可见顶点数组vertex[4]={v0,v1,V2,V3}，弧数组arc[4][4]也是一个矩阵，但因为是有向图，所以这个矩阵并不对称，例如由V1到VO有弧，得到arc[1][0]=1，而V0到V1没有弧,因此
arc[0][1]=0。
另外有向图是有讲究的，要考虑入度和出度,顶点V1的入度为1，正好是第V1列的各数之和，顶点V1的出度为2，正好是第V2行的各数之和。

 邻接矩阵（网)
在图的术语中，我们提到了网这个概念，事实上也就是每条边上带有权的图就叫网。

 这里“○o”表示一个计算机允许的、大于所有边上权值的值。

邻接表(无向图)
因此我们可以考虑另外一种存储结构方式，例如把数组与链表结合一起来存储,这种方式在图结构也适用，我们称为邻接表(AdjacencyList)。

邻接表的处理方法是这样:
一图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。
一图中每个顶点Vi的所有邻接点构成一个线性表，由于邻接点的个数不确定，所以我们选择用单链表来存储。

 若是有向图，邻接表结构也是类似的，我们先来看下把顶点当弧尾建立的邻接表,这样很容易就可以得到每个顶点的出度:

 但也有时为了便于确定顶点的入度或以顶点为弧头的弧,我们可以建立一个有向图的逆邻接表:

 邻接表(网)
对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值即可:

 十字链表

邻接表固然优秀，但也有不足，例如对有向图的处理上,有时候需要再建立一个逆邻接表~
那我们思考了:有没有可能把邻接表和逆邻接表结合起来呢?
答案是肯定的，这就是我们现在要谈的十字链表(Orthogonal List)
为此我们重新定义顶点表结点结构:

 接着重新定义边表结点结构:

蓝色线是出度，红色线是入度。 

 

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

邻接多重表
因此,我们也仿照十字链表的方式，对边表结构进行改装，重新定义的边表结构如下:

其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边，jLink指向依附顶点jVex的下一条边。

也就是说在邻接多重表里边，边表存放的是一条边，而不是一个顶点。

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