图其实就是顶点和边的集合，所以说，图的存储本质就是存储图的顶点和边。
1. 邻接矩阵
顶点存储在一维数组中
边存储在二维数组（矩阵）中，arc[v][w]表示的就是v到w的边
如果v到w的边存在则存储边的权值，如果不存在则标为无穷
2. 邻接表
稀疏图存在的边是很少的，有向图的邻接矩阵是对称的。所以，这两种情况下使用邻接矩阵存储边都是很浪费空间的。
因此可以使用邻接表，类似于树的孩子表示法。顶点中有指针域，指向邻顶点的链表，与该顶点相邻的顶点依次在链表中排序
Paste_Image.png
有向图中，需要用两个邻接表存储边，邻接表与逆邻接表。用于分别存储不同方向的边（出边和入边）。
3. 十字链表
专用于有向图，解决邻接表需要两个邻接表的问题。
形如邻接表，但链表结点的结构有所不同，且除了出边链表，还有入边链表
链表结点结构
tailVex：弧指向的结点
headVex：弧出发的点
headLink：指向入边链表的下一个结点
tailLink：指向出边链表的下一个结点
可以理解为，一个链表结点（等于是一条表）同时存在两个链表当中，因此整个十字链表是，所有链交织成一张网。
十字链表
4. 邻接多重链表
无向图优化存储结构，无向图的边是对称的，在邻接表中，<v1,v2>,<v2,v1>表达的是同一条边。除了占用存储空间外，删除，添加边的时候也很麻烦，对一条边的操作，要处理两次。
邻接多重链表其顶点指向的是一条边，而非一个链表。
边的存储结构
iVex，jVex分别是边的结点
iLink是指向iVex结点的下一条边的指针
jLink是指向jVex结点的下一条边的指针
邻接多重表
如果要遍历一个顶点的所有边，从顶点的指针指向的第一条边出发。然后找到边中与顶点相对应的指针，找下一条边。
5. 边集数组
边集数组
就是如此简单粗暴地把顶点和边存储，但后期还原图的时候需要多次的遍历，存储结构简单，但是操作图就变得复杂了。
网友评论