问题(数据结构):
我们应该使用哪种表示来计算 O(|V|+|E|) 中图顶点的入度？这应该如何在 Khan 的算法中保持而不损害运行时间(渐近地)？证明您的主张。
我的尝试: 我们应该使用矩阵表示来计算入度，因为邻接表只在顶点和它们的外度之间相关，而矩阵在两者之间相关，因此我们应该使用矩阵来计算入度.我在问题的第二部分遇到困难。
你能帮忙吗？
提前致谢!
最佳答案
你只需要一个数组。
您可以通过遍历所有边并增加每条边末端的入度来填充它。
之后，处理一个节点后，只需要将该节点的所有邻居的入度减一即可。
邻接表可能是解决这个问题最方便的图形存储格式。
关于algorithm - 在不影响运行时间的情况下维护可汗算法(渐近)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43563631/