谈谈图

今天说一个在《数据结构》这么课程中特别重要的数据结构,即图,其具体形象如下图所示。

图具有2种表示方式,分别是邻接矩阵和连接表。

先说说邻接矩阵,如下图所示,假如图的节点数为n,其实就是一个二维数组arr[n][n],若节点i和节点j之间有连线时,arr[i][j]=1,同理,在无线图中,此时节点j和节点i之间也是有连线的,arr[j][i]=1,反之,若节点i和节点j之间没有连线时,arr[i][j]=0,同理,在无线图中,此时节点j和节点i之间也是没有连线的,arr[j][i]=0。在下图可以看出,i节点和i节点之间是默认没有连线的,arr[i][i]=0。另外,这个矩阵关于对角线对称。

看看代码。

如上图所示,adjIterator为SparseGraph的内部类,这个类是用来对SparseGraph遍历的,上述代码已经有详细注释了,这里就不进行赘述了。

邻接表,如下图所示,其实就是一个链表数组,数组的每一个元素都是一个链表,而每个链表的表头都是一个节点,其链表中的元素都是与这个链表的表头即这个节点相连的节点。若节点i与节点j、k、z有直线相连,而在以i为表头的链表中,存在着j、k、z这3个元素。

邻接表相对于邻接矩阵相比,是节省了不少的空间,但这也并非意味着邻接矩阵毫无用武之地。一般来说,邻接表适合表示一个稀疏图,而邻接矩阵适合表示一个稠密图。

看看代码。

如上图所示,DenseGraph也有adjIterator这个内部类内部类,这个类是用来对DenseGraph遍历的,上述代码已经有详细注释了,这里就不进行赘述了。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180330G1QEN900?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券