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 Shubhanshu commented Apr 28, 2017 reply Follow Share but in this, If I want to find the out-degree of 4 then first I have to search for the 4 in the head (an array of pointers) then in that I have to traverse each node arranged in linked list format to count the out-degree which will take O(V) time in worst case when the graph is complete graph. rt?? 0 votes 0 votes Prashant. commented Apr 28, 2017 reply Follow Share it takes (m+n) ryt? if complete graph then m= n2 i.e. n*n matrix is full. so it takes O(n2) 0 votes 0 votes Shubhanshu commented Apr 28, 2017 i edited by Shubhanshu Apr 29, 2017 reply Follow Share Please tell me how it is O(V+E) for adj list step by step? because it is becoming complex for me. Ok, I got it after study Cormen and various different sources I come to know that its time is O(V+E) by the following observation- For BFS Time Calculation considering your graph:- Time complexity = (Time to enqueue and dequeue every vertex + time to scan adjacency list for the vertex which is going to enqueue or dequeue i.e current vertex). so it is O(V+E) for BFS. Now For In degree and out degree- Suppose I want to find degree of vertex v then just go to array i.e head like Head[v] { this will take constant time } and then scan the list there { this will take some time lets say dv } now for each vertex constant time and for all vertex O(V) time and scan list will take calculation as follow dv + dv + dv + ....... + dv = 2E = O(E) so in the total time is O(V+E) for undirected graph right? 1 votes 1 votes Prashant. commented Apr 29, 2017 reply Follow Share yes .... 0 votes 0 votes Shubhanshu commented Apr 29, 2017 reply Follow Share Big Thanks to you..... but in the question, they are asking about directed graph. it is easy to calculate in-degree and out-degree in the undirected graph since for each vertex in-degree = out-degree and can be calculated by just traversing the list of the corresponding vertex. And similar approach can be used for out degree of a vertex in the directed graph. but how in-degree be calculated in a directed graph. 1 votes 1 votes Prashant. commented Apr 29, 2017 reply Follow Share Directed graph can also be stored in adjacency list see above image. Visit linked list and if you find that element you will get its in-degree. like for vertex 3 we see 3 comes in right hand side of vertex 1 and vertex 2. so in-degree is 2. 2 votes 2 votes Shubhanshu commented Apr 29, 2017 reply Follow Share But for searching 3 on the right-hand side of the list we have to traverse each vertex corresponding list. which will take O(V+E) for finding in-degree of 3 only. 1 votes 1 votes Prashant. commented Apr 29, 2017 reply Follow Share Take extra array fill it with 0 initially. Now visit all vertex and edges 1 time only i.e. when you visit row for vertex 1 then increment position by 1 when you get any vertex. like you see 2 put 1 on place a[2] , then see 3 put a[3] = 1, then see 4 then [4]= 1 come for 2 , you see 3 again now a[3]= 1+1= 2. etc like that you have to visit graph only once to find in-degree of every vertex 4 votes 4 votes 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.