邻接列表中的边缘长度

Question

将边缘长度放在邻接列表实现中的最佳位置是哪里？ I using this site as reference。我在想的是将它放在边缘节点中，以便找到从一个顶点到另一个顶点的长度，然后转到其中一个顶点节点并找到其连接边并访问相关成员。 （请参阅链接页面上的第5部分：“用于实现的数据类型”）

这听起来对我来说很合理，但我浏览了很多网站，没有网站证实这是有效的。我还记得在某个地方看到，在相邻矩阵中实现长度要容易得多，但没有说是否可以在邻接列表中实现长度，或者更难。

Answer 1

edgeTag是边缘长度的理想场所。关于图的表示，它取决于你的需求 - 对于稀疏图（邻接节点你必须检查它们全部），邻接矩阵是无效的，尽管使用它更容易一些。