图的几种表示方法

标签:距离   lan   数据结构   解决   比较   复杂   问题   冗余   矩阵   

1. 邻接矩阵

//设有矩阵e[n][n],其中n是图中点的数量,
//则e[i][j]表示从点i到点j的距离(边的权重)

2.邻接表

因为图可能不是完全的,所以有很多的点之间互相并没有边相连,这种情况下若使用邻接矩阵,无疑会造成空间的浪费。

所以不妨采用列表的方式存储。

可以有两个思路

  1. 列表套列表,但是在边存在权重的问题中,需要新建数据结构,来存储一个点的序号和边权重。
  2. map套map,两层map可能看起来比较复杂,但是直接解决了冗余问题,节省了空间,而且思路上非常直观。

图的几种表示方法

标签:距离   lan   数据结构   解决   比较   复杂   问题   冗余   矩阵   

原文地址:https://www.cnblogs.com/agnes6/p/13940401.html

版权声明:完美者 发表于 2020-11-07 17:29:41。
转载请注明:图的几种表示方法 | 完美导航

暂无评论

暂无评论...