2 votes 2 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 in-degrees? Algorithms graph-algorithms time-complexity + – Shubhanshu asked Apr 28, 2017 • retagged Jun 24, 2022 by makhdoom ghaya Shubhanshu 2.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes Consider the given Graph and its Adjacency list. Procedure to fill Adjacency list apply BFS algorithm. On every vertex will give you all vertex which are directly connected to That vertex. which take O(m+n) time . Now if i want to find in-degree of any vertex then just go to that vetrex and go to corresponding row to that vertex which will take O(n+m) time in worst case . Prashant. answered Apr 28, 2017 • selected Apr 29, 2017 by Shubhanshu Prashant. comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Shubhanshu commented Apr 29, 2017 reply Follow Share Thank you so much..... 1 votes 1 votes Xylene commented Aug 17, 2017 reply Follow Share Using adjacency list, for undirected and directed graph, computing indegree and outdegree of a vertex requires O(V+E) time. Using adjacency matrix, for undirected and directed graph, computing indegree and outdegree of a vertex requires O(V) time. Am I correct? 0 votes 0 votes reboot commented Dec 18, 2020 reply Follow Share @Xylene Not it will be O($V^{2}$) 0 votes 0 votes Please log in or register to add a comment.