#version 2 本版本实现的邻接表是基于开放定址法的哈希表,此次实现应该基本与标准方法相同:
- 哈希表开辟的空间为顶点V,使用线性探测法解决冲突(缺点是插入最后几个顶点时效率比较低,插入边效率同样低下,为O(V))
- 在实现入度表时,直接使用int数组,将复杂度降为了O(V)
- 进行入度统计时,算法复杂度时O(V+E)
- 拓扑排序复杂度同样为O(V+E)
本次修改之前,仔细考虑了如何降低插入顶点与边的开销,最后发现如果顶点名字是字符串的话,没法降低。只有把顶点定义为int,直接对顶点结构体数组进行寻址才可以做到。所以插入顶点的与边的开销不能算实现的缺陷。