一天一个数据结构知识——邻接矩阵、邻接表

(资料图)

邻接矩阵的图的表示方法里最简单的一个，在它的存储结构就是由一个存放顶点的数组和一个二维数组组成。图的表示方法也很简单，如果两个顶点间有边（或弧），二维数组对应位置的值就设为1，反之则为零。

这样的话，对于无向图，如果想要求得一个顶点的度，只需遍历求和其对应行或列的非零元素，其复杂的是O(n)。类似地，对于有向图，若要求出度，则遍历顶点对应行，求入度则遍历顶点对应列。度则是入度和出度的和。

而对于带权图的存储结构，只需给二维数组的对应节点赋值为对应的权值，其余无边的节点设为无穷即可，对于无穷的定义可以通过宏定义一个最大值来将其当作无穷。

了解完邻接矩阵的定义之后，下面开始分析其性能。首先，其空间复杂度为O（|v|^2）,适合存储稠密图。

虽然邻接矩阵如此简单，但是其仍有许多优良的性质可以方便我们计算。若矩阵元素为0/1的邻接矩阵为A，那么A^n[i][j]就是从i顶点到j顶点的长度为n的路径的数目。多么好的性质！对于这个性质的理解，我们可以先从A^2开始理解。比如，有ABCD四个点，从A到D长度为2的路径可能有AA-AD,AB-BD，AC-CD,AD-DD，如果AB-BD路径存在那么A-B和B-D对应的邻接矩阵的值均为1，其相乘也为1，而矩阵矩阵的乘法求得的A^2[1][4]恰好就是以上对应的点相乘再相加，自然就是路径数目，A^n也可以以此类推。

邻接表的表示方法和树的孩子表示法类似，即可用一个一维数组存储结点的信息，用链表存放一个和结点相连的边。而有向图和无向图的区别在于，无向图每个边都存放了两遍，有向图只存放结点向外的边，每条边只存放一边，有向图的入度也因此不好计算。