关于邻接矩阵和邻接表
来源：7-2 图的表示
邹正霖
2020-11-18
这里我存在三个问题：
- 为什么邻接矩阵不好处理自环边问题？
假设有自环边，g[v][w] = true不行吗？会存在什么问题？ - 邻接矩阵 hasEdge 函数中，添加边之前不判断是否已经存在边也可以吧？
有多条边也是有这种情况的吧，是因为课程中的图就是简单图吗？ - 为什么邻接表中 hasEdge 函数中，添加边之前不判断是否已经存在有边？
是因为复杂度的原因吗？
谢谢老师 ！
写回答
1回答
-
1）没有问题。我在课程的什么 context 下说邻接矩阵不好处理自环边了？给我一个位置？我再看一下？
2）可以呀。课程中的测试用例只局限于简单图，不代表图的表示只支持简单图。
3）邻接矩阵不需要判断；邻接表是复杂度的原因，在最差情况下会使得添加边的操作变为 O(n) 级别。
继续加油！：）
012020-11-18
相似问题