Cormen

Question

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?

Answer 1

1. Consider the given Graph and its Adjacency list.

1. 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 .
2. 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 .

Comments

Thank you so much.....

---

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?

---

@Xylene Not it will be O($V^{2}$)