Maintain in Hahn's algorithm without sacrificing runtime (asymptotically)
Question (data structure):
Which representation should we use to compute the in-degrees of the vertices of a graph in O (| V | + | E |)? How should this be maintained in Khan's algorithm without damaging the runtime (asymptotically)? Prove your claims.
My attempt: We have to use the matrix representation to calculate in-degrees, because the adjacency list only refers to the vertices and their outer degrees, while the matrix is related between them, and for this reason, we must use the matrix to calculate in-degrees. I'm having a hard time in the second part of the question.
You can help?
Thanks in advance!
source to share
You need an array.
You can fill it up by iterating over all edges and increasing the degree at the end of each edge.
After that, you just need to decrease the degree of all the neighbors of the node by one after processing the node.
An adjacency list will probably be the most convenient graph storage format for this problem.
source to share