邻接矩阵怎么转化为连通图,图的邻接矩阵怎么输入

首页 > 手工 > 作者:YD1662023-05-05 08:17:10

有向图的数组存储主要有以下特性:

(1)顶点数组长度为图的顶点数目n。边数组为n X n的二维数组。(2)边数组中,数组元素为1,即A[i][j] = 1,代表第i个顶点与第j个顶点邻接,且i为尾,j为头。 A[i][j] = 0代表顶点与顶点不邻接。(3)在有向图中,由于边存在方向性,因此数组不一定为对称数组。(4)对角线上元素为0。(5)第i行中,1的数目代表第i个顶点的出度。例如:顶点V1的出度为2,则顶点V1所在行的1的数目为2。(6)第j列中,1的数目代表第j个顶点的入度。例如:V3的入度为1,则V3所在列中1的数目为1。

数组存储方式优点:

数组存储方式容易实现图的操作。例如:求某顶点的度、判断顶点之间是否有边(弧)、找顶点的邻接点等等。

数组存储方式缺点:

采用数组存储方式,图若有n个顶点则需要n2个单元存储边(弧),空间存储效率为O(n2)。 当顶点数目较多,边数目较少时,此时图为稀疏图,这时尤其浪费空间。

例如:图5.3所示的图,图中有 9 个顶点,边数为10,需要 9X9 的二维数组,而实际存储边信息空间只有10,造成空间浪费。

邻接矩阵怎么转化为连通图,图的邻接矩阵怎么输入(13)

图5.3所示无向图的存储数组:

邻接矩阵怎么转化为连通图,图的邻接矩阵怎么输入(14)

6 邻接表

当使用数组存储时,主要有以下三个问题:

(1)对于一个图,若图中的顶点数目过大,则无法使用邻接矩阵进行存储。因为在分配数组内存时可能会导致内存分配失败。(2)对于某些稀疏图(即顶点数目多,边数目少),创建的数组大小很大,而真正存储的有用信息又很少,这就造成了空间上的浪费。 (3)有时两个点之间不止存在有一条边,这是用邻接矩阵就无法同时表示两条以上的边。

针对以上情况,提出了一种特殊的图存储方式,让每个节点拥有的数组大小刚好就等于它所连接的边数,由此建立一种邻接表的存储方式。

邻接表存储方法是一种数组存储和链式存储相结合的存储方法。在邻接表中,对图中的每个顶点建立一个单链表,第 i 个单链表中的结点依附于顶点 Vi 的边(对有向图是以顶点Vi为尾的弧)。链表中的节点称为表节点,共有 3个域,具体结构见下图:

邻接矩阵怎么转化为连通图,图的邻接矩阵怎么输入(15)

除表节点外,需要在数组中存储头节点头结点由两个域组成,分别指向链表中第一个顶点和存储Vi的名或其他信息。具体结构如下图:

邻接矩阵怎么转化为连通图,图的邻接矩阵怎么输入(16)

上一页12345下一页

栏目热文

文档排行

本站推荐

Copyright © 2018 - 2021 www.yd166.com., All Rights Reserved.