图的存储结构

图的存储结构也叫图的存储表示和图的表示，主要介绍3种：邻接矩阵、邻接表、边集数组
1、邻接矩阵（adjacency matrix）表示图形中顶点之间相邻关系的矩阵。amx[i,j]=1,表示i,j之间存在边的关系，若为0则表示二者之间无边的关系。无向图的邻接矩阵是按照主对角线对称的，
有向图则不是。若是带权图，则把1换成相应的权值即可。
因邻接矩阵中的元素可以随机存取，所以查找一条边的时间复杂度为O(1)。
由于求任一顶点的度需要访问对应一行或者一列中的所有元素，所以其时间复杂度为O(n)；
图的邻接矩阵的存储需要暂用n*n个实数存储空间，所以其空间复杂度为O(n^2)。若用于存储稠密图能够充分利用存储空间，但若是用于表示稀疏图，则使邻接矩阵变为稀疏矩阵，从而造成存储空间的很大浪费。
2、邻接表（adjacency matrix）是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用一维数组（向量）存储的一种图的表示方法。邻接表中每个结点用来存储一条边的信息，因而称之为边结点。边结点通常包含3个域：邻接点域，用来存储顶点的一个邻接顶点的序号；权值域，用来存储边上的权；邻接域，用来存储邻接表中的下一个边结点。
每个顶点单链表的平均长度为e/n（对于有向图）或2e/n(对于无向图)，其中e是边数，n是点数。所以查找运算的时间复杂度为O(e/n)。对于需要经常查找顶点入边或入边邻接点的运算，可以专门建立一个逆邻接表，该表中每个顶点的单链表不是存储该顶点的所有出边的信息，而是存储所有边的入边信息，邻接点域存储的是入边邻接点的序号。
3、边集数组（edgeset array）是利用一维数组存储图中所有边的一种图的表示方法。数组中的每个元素存储一条边的起点、终点（对于无向图，可选定边的任一端点为起点或终点）、和权值，边的的信息在数组中可以任意安排。边集数组中只存储图中所有边的信息，若需要存储顶点的信息，同样需要一个具有n个元素的一维数组。在边集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以时间复杂度是O(e)，空间复杂度为O(e)。从空间复杂度上讲，边集数组也适合表示稀疏图。
图的遍历：深度优先+广度优先
深度优先搜索遍历（depth-first search）：类似于树的先序遍历，是一个递归的过程。对图进行深度优先搜索遍历时得到的顶点序列不是唯一的。图的深度优先搜索遍历的过程分为两个函数定义来实现，一个驱动函数，另一个工作函数。驱动函数为一个非递归函数，它起到与外界接口和调用内部递归函数的作用；工作函数是只允许在图类内部调用的私有递归函数，该函数具体完成对图中每个顶点的访问任务。
对邻接矩阵表示的图进行深度优先搜索遍历时，可能需要扫描邻接矩阵中的每一个元素，其时间复杂度为O(n^2)；对邻接表表示的图进行深度优先遍历时，可能需要扫描邻接表中的表头数组的每个元素和所有边结点，其时间复杂度为O(n+e)；二者的空间复杂度均为O(n)
广度优先搜索遍历（breadth-first search）：类似于树的按层遍历。
同样对图的广度优先遍历也要两个函数，一是用于外部接口的驱动函数，二是完成访问所有顶点的工作函数；
在工作函数中需要使用一个队列，用来依次记住被访问过的顶点。函数开始时，对初始点访问后插入队列中，以后每从对队列中删除一个元素，就依次访问它的每一个未被访问过的邻接点，并令其进队，这样，当队列为空时，表明所有与初始点有路径相通的顶点都已访问完毕，算法就结束了。
对于非连通图，需要以图中未被访问到的每一个顶点作为起始点，再次调用搜索遍历方法即可；