图的存储结构：邻接矩阵法

邻接矩阵法：邻接矩阵的定义：邻接矩阵存储无向图：邻接矩阵存储有向图：邻接矩阵存储网：邻接矩阵法的性质：邻接矩阵法的代码实现：矩阵运算A的n次幂的含义：性能分析：

邻接矩阵法：

邻接矩阵的定义：

注：其实就是一个二维数组，用二维数组的值表示这俩个节点是否存在边

邻接矩阵存储无向图：

ps：无向图的矩阵必定为对称矩阵，所以可以压缩成上三角存储

邻接矩阵存储有向图：

邻接矩阵存储网：

ps：其实和存储图类似，只不过把要存储的值换成了边的权重

例：

PS:无穷的表示：#define INFINITY //int的最大值

邻接矩阵法的性质：

行：在有向图中，一个节点到另一节点的入度

列：在有向图中，一个节点到另一节点的出度

邻接矩阵法的代码实现：

//空间复杂度O(n2)#define MaxVertexTypeNum 100typedef char VertexType;//顶点的类型 typedef int EdgeType;//边的类型 typedef struct{VertexType Vex[MaxVertexTypeNum];//存放顶点的一维数组 EdgeType Edge[MaxVertexTypeNum][MaxVertexTypeNum];//存放边的二维数组 int vexnum,arcnum;//顶点个数 }MGraph;

矩阵运算A的n次幂的含义：

例：

第一个11表示从B到E的一条路径

第二个11表示从B到E的另一条路径

结论：An[i][j] 表示从顶点Vi到顶点Vj长度为n的路径的条数

性能分析：

空间复杂度：O(|v|^2)

如果觉得《数据结构之图的存储结构：邻接矩阵法》对你有帮助，请点赞、收藏，并留下你的观点哦！