老师，邻接表不考虑边的重复添加嘛

Question

老师，邻接表不考虑边的重复添加嘛，为什么不判断一下，就m++了

Answer 1

liuyubobobo 2018-03-26 04:08:18

是的哦，在这个课程中的代码，相当于是允许邻接表有重边的。只不过我们后续算法的测试用例中，将不存在有重边的测试用例：）

如果一定要排除邻接表的重边，可以在addEdge的时候，添加一定的逻辑，进行查重处理。不过对于vector<vector<int>>的设计，对于每个点的邻边，在vector中进行查重是O(n)的复杂度，比较耗时。如果需要处理这种情况，应该将邻接表声明成vector<unordered_map<int, int>>的方式，这样，每次查重工作是O(1)的时间复杂度。对于相应的可能产生的更多问题，已经超出这个课程的范畴了。我有机会一定出一门专门的图论算法课程，给大家系统加讲讲图论这个领域：）

另外，这个课程的代码中，邻接矩阵和邻接表的实现，也是允许自环边的哦。不过按照这个课程的代码，无向图的邻接矩阵的实现不支持重边。如果需要在邻接矩阵中支持重边，就应该使用vector<vector<int>>代替vector<vector<bool>>，其中g[i][j]是一个整数，表示从i到j之间的边数：）

• 提问者 AlbertRui #1

  谢谢老师！