问题（数据结构）：
我们应该使用哪种表示来计算图的顶点在o（v+e）中的度数？在khan的算法中，如何在不影响运行时间的情况下（渐近地）保持这一点？证明你的主张。
我的尝试：
我们应该使用矩阵表示来计算in度，因为邻接表只与顶点及其外部度数相关，而矩阵则与顶点及其外部度数相关，因此我们应该使用矩阵来计算in度。我在问题的第二部分有困难。
你能帮忙吗？
提前谢谢！
最佳答案
你只需要一个数组。
可以通过迭代所有边并增加每条边末端的in度来填充它。
之后，您只需要在处理节点后将该节点的所有邻居的in度减少一个。
对于这个问题，邻接列表可能是最方便的图形存储格式。
关于algorithm - 维持Khan算法而不影响运行时间(渐近)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43563631/