为什么要迭代器来遍历

Question

不能像二叉树的遍历一样在类中进行么，为什么要在外面遍历。

还有。稀疏图在这里的遍历应该是O(E*V)吧

Answer 1

liuyubobobo 2017-06-18 02:29:19

因为我们后续要介绍的图算法，都是既对稀疏图成立，也对稠密图成立的。我们使用这样的一个迭代器，使得两种图的表示中，对于“遍历一个顶点的相邻顶点”这个操作，将其接口进行了统一。很快你就会看到，这样一来，对于同一个算法，我们的代码是统一的，而不用去考虑用户传进来的图是邻接矩阵的表示法还是邻接表的表示法。在之后的具体算法上，你可以思考一下，如果没有这个迭代器，我们的每一个算法针对处理的具体是稀疏图还是稠密图，代码就会有微小的不同。

不过这样的设计其实过于OO了。在我们的后续算法中，大量使用了泛型，其实也影响了算法性能。在很多时候，这样的设计是没必要的。在这里了解这个思路就好。因为迭代器本身是非常重要也实用的设计方式。具体到图算法，在我们的后续算法，其实完全可以只实现一个稀疏图的版本。因为在大多数情况下，我们处理的都是稀疏图。

稀疏图的遍历是O(V+E)的，每一个顶点和每一条边都访问一遍。

• 提问者 易萧 #1

  非常感谢！

Answer 2

Joseph731 2018-06-23 19:19:16

还是不太明白为什么dense里面index 要等于-1，波波老师可以帮我解答一下吗

• liuyubobobo #1

  请参考这里：http://coding.imooc.com/learn/questiondetail/65015.html ：） 加油！