0 votes 0 votes Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex ? How long does it take to compute the in-degrees ? Algorithms cormen algorithms graph-algorithms descriptive + – akash.dinkar12 asked Apr 7, 2019 akash.dinkar12 360 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes To compute the out degree each vertex we would need $O(V+E)$. To compute the in degree we have to scan through adjacency lists and count how many times each vertex has appeared. This is $O(V+E)$ Vineet Kumar 1 answered Apr 7, 2019 Vineet Kumar 1 comment Share Follow See all 0 reply Please log in or register to add a comment.