图的存储

邻接矩阵 Vextex/Vertices 顶点; Martix 矩阵; Arc 弧. 代码实现 #define MaxVextexNum 100//容许存储的最大顶点数 typedef struct{ char Vex[MaxVextexNum]; //可以将定点之间的关系用int 类型01表示,也可定义为boolean/枚举类型,占空间更小 bool Edge[MaxVextexNum][MaxVextexNum]; int vexnum,arcnum;//顶点数和弧|边数 }MGraph; 即 找度 根据邻接矩阵计算结点的度TD 无向图 有向图 $TD(V_i)$ 第i行(或i列)中非零元素的个数 $ID(V_i)$ : i行非零元素个数 $OD(V_i)$: i列非零元素个数 TD=ID+OD 对于带权图(网) #define MaxVextexNum 100//容许存储的最大顶点数 #define INIFINITY //宏定义,表示无穷 typedef char VextexType;//顶点 typedef int EdgeType;//权值 typedef struct{ VextexType Vex[MaxVextexNum]; EdgeType Edge[MaxVextexNum][MaxVextexNum]; int vexnum,arcnum; }MGraph; 复杂度 空间复杂度来自数组Vex[]跟Edge[],故空间复杂度为$|V|+|V|^2=O(|V|^2)$,即为顶点数量的二次方,故此方法更适合存储稠密图,不然有较多浪费。...

Jun 2, 2021 · 1 min · Archai