【数据结构】图的存储-邻接矩阵法、邻接表法、十字链表与邻接多重表（上）

1. 邻接矩阵

#define MaxVertexNum 100  // 顶点数目的最大值
typedef struct{
    char Vex[MaxVertenNum];  // 顶点表
    int Edge[MaxVertenNum][MaxVertexNum];  // 邻接矩阵，边数
    int vexnum,arcnum;  // 图的当前顶点数和边数/弧数
}MGraph;

结点数为n的图G=(V,E)的邻接矩阵A是n*n的，将G的顶点编号为v1,v2,…,vn，则

思考

如何求顶点的度、入度、出度？

对无向图而言：

第i个结点的度=第i行（或第i列）的非零元素个数。

对有向图而言：

第i个结点的出度=第i行的非零元素个数

第i个结点的入度=第i列的非零元素个数

第i个结点的度=第i行、第i列的非零元素个数之和

邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)

1. 邻接矩阵法存储带权图（网）

#define MaxVertexNum 100  // 顶点数目的最大值
#define INFINITY   // 宏定义常量“无穷”  用int的上限值表示“无穷”
typedef char VertexType;  // 顶点的数据类型
typedef int EdgeType;  // 带权图中边上权值的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];  // 顶点
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  // 边的权
    int vexnum,arcnum;  // 图的当前顶点数和弧数
}MGraph;

2. 邻接矩阵法的性能分析

空间复杂度： 只和定点数有关，和实际的边数无关。

适合用于存储稠密图。

无向图的邻接矩阵是对称矩阵，可以压缩存储（只存储上三角区/下三角区）。

3. 邻接矩阵法的性质

含义：对于第一个式子，表示从A到D的路径长度为2的路径有1条。对于第2个式子，表示从B到B的路径长度为2的路径有3条。

含义：对于红点标识的数字1，表示从A到D的路径长度为2的路径有1条。对于蓝点标识的数字1，表示从B到D的路径长度为1的路径有1条。

含义：对于红点标识的数字1，表示从A到D的路径长度为3的路径有1条。对于蓝点标识的数字4，表示从B到D的路径长度为3的路径有4条。

备注：离散数学。