92图的存储结构邻接矩阵表示法 0123 0 0 0000 G1=2 0001 3 000 第i行元素的值:表示是否有从顶点v出发到图中其他顶点的弧 (即以v为尾的弧),若有则相应位置上的值为1,否则为0; 第i列元素的值:表示是否有从图中其他顶点出发到顶点v的5弧 (即以v为头的弧),若有则相应位置上的值为1,否则为0 A中第i行元素之和 ☆有向图中:顶点V的出度= 顶点V的入度=A中第列元素之和 16
启迪管理课程 16 9.2 图的存储结构－－邻接矩阵表示法 v0 v1 v2 v3 G1 A中第i行元素之和 A中第i列元素之和 0 1 2 3 = 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 AG1 0 1 2 3 ❖有向图中：顶点Vi的出度= . 顶点Vi的入度= . 第i行元素的值：表示是否有从顶点vi出发到图中其他顶点的弧 （即以vi为尾的弧），若有则相应位置上的值为1，否则为0； 第i列元素的值：表示是否有从图中其他顶点出发到顶点vi的弧 （即以vi为头的弧），若有则相应位置上的值为1，否则为0
92图的存储结构邻接矩阵表示法 网的要矩阵定义为: Ail门 若(V1,V )或<v,v1>∈VR 反之 或 若(v,v或<v,v>∈VR x其他012345 ● 5 0 5 7 28 5 5 5|3 ○ 17
启迪管理课程 17 9.2 图的存储结构－－邻接矩阵表示法 网的邻接矩阵定义为： V0 V1 V5 V2 V4 V3 5 8 4 7 5 5 1 3 N = 3 1 5 5 8 4 5 7 AN 0 1 2 3 4 5 0 1 2 3 4 5 = 反之 w 若 v v 或 v v VR A i j i j i j i j ( , ) , [ ][ ] , = = 其他 若 或 i j i j i j i j v v w v v v v VR A i j 0 ( , ) , [ ][ ] , 或
92图的存储结构邻接矩阵表示法 ●矩件的特点如下 (1)图的邻接矩阵表示是惟一的。 (2)无向图的邻接矩阵一定是一个对称矩阵。因此 按照压缩存储的思想,在具体存放邻接矩阵时只需存 放上或下)三角形阵的元素即可 (3)不带权的有向图的邻接矩阵一般来说是一个稀 疏矩阵,因此,当图的顶点较多时可以采用三元组表 的方法存储邻接矩阵。 (4)对于无向图接矩阵的第行(或第列准非零元 素或∞元素)的个数正好是第个顶点v的度。 18
启迪管理课程 18 9.2 图的存储结构－－邻接矩阵表示法 ⚫邻接矩阵的特点如下： (1) 图的邻接矩阵表示是惟一的。 (2) 无向图的邻接矩阵一定是一个对称矩阵。因此, 按照压缩存储的思想,在具体存放邻接矩阵时只需存 放上(或下)三角形阵的元素即可 (3) 不带权的有向图的邻接矩阵一般来说是一个稀 疏矩阵,因此,当图的顶点较多时,可以采用三元组表 的方法存储邻接矩阵。 (4) 对于无向图,邻接矩阵的第i行(或第i列)非零元 素(或非∞元素)的个数正好是第i个顶点vi的度
92图的存储结构邻接矩阵表示法 ●接矩阵的特点如下 (5)对于有向图,接矩阵的第(或第砂)非零元 素或非∞元素)的个数正好是第个顶点v的出度或入 度) (6)用邻接矩阵方法存储图很容易确定图中任意 两个顶点之间是否有边相连。但是,要确定图中有多 少条边则必须按行、按列对每个元素进行检测,所花 费的时间代价很大。这是用邻接矩阵存储图的局限性。 19
启迪管理课程 19 9.2 图的存储结构－－邻接矩阵表示法 ⚫邻接矩阵的特点如下： (5) 对于有向图,邻接矩阵的第i行(或第i列)非零元 素(或非∞元素)的个数正好是第i个顶点vi的出度(或入 度)。 (6) 用邻接矩阵方法存储图,很容易确定图中任意 两个顶点之间是否有边相连。但是,要确定图中有多 少条边,则必须按行、按列对每个元素进行检测,所花 费的时间代价很大。这是用邻接矩阵存储图的局限性
92图的存储结构邻接矩阵表示法 ●数组表示法的存字信结构描述 # define maxv<最大页点个数> # define NfINitY NT maX最大值 typedef struct int no; /顶点编号* InfoType info; 八顶点其他信息 Ⅴ ertex'lype /顶点类型* 20
启迪管理课程 20 9.2 图的存储结构－－邻接矩阵表示法 ⚫数组表示法的存储结构描述： #define MAXV <最大顶点个数> #define INFINITY INT_MAX //最大值∞ typedef struct { int no; /*顶点编号*/ InfoType info; /*顶点其他信息*/ } VertexType; /*顶点类型*/