关于邻接矩阵和邻接表

Question

这里我存在三个问题：

1. 为什么邻接矩阵不好处理自环边问题？
   假设有自环边，g[v][w] = true不行吗？会存在什么问题？
2. 邻接矩阵 hasEdge 函数中，添加边之前不判断是否已经存在边也可以吧？
   有多条边也是有这种情况的吧，是因为课程中的图就是简单图吗？
3. 为什么邻接表中 hasEdge 函数中，添加边之前不判断是否已经存在有边？
   是因为复杂度的原因吗？

谢谢老师 ！

Answer 1

liuyubobobo 2020-11-18 20:38:53

1）没有问题。我在课程的什么 context 下说邻接矩阵不好处理自环边了？给我一个位置？我再看一下？

2）可以呀。课程中的测试用例只局限于简单图，不代表图的表示只支持简单图。

3）邻接矩阵不需要判断；邻接表是复杂度的原因，在最差情况下会使得添加边的操作变为 O(n) 级别。

继续加油！：） 

• 提问者 邹正霖 #1

  我又看了一遍视频，是我理解错了，将代码实现了一遍，思考过后比较理解了（tips:老师每次回答都好快啊）