Given an adjacencylist representation of a directed graph, how long does it take to compute the outdegree of every vertex? How long does it take to compute the indegree?
Answer:
The outdegree of a vertex is
the number of edges leaving it. By definition an edge consists of a pair of
vertices (note: Can be selfloops) and for the directed graph G = (V, E)
consists of an array of adjacency of V lists such as adjacencylist [u] u Î V. That means the time taken to compute the outdegree
will be equal to the time it takes to search through the adjacencylists for
that vertex. If the adjacencylists have n vertices then the time taken will be
the same as the search time for binary tree O(n). (See textbook page 253 for
explanation).
Similarly the time takes to compute the indegree is O(n)
Redo exercise 2.11:
Reference: COMP510 Fall 2005: HW 9 Collaboration
To
compute for the Outdegree of every vertex, O(E+V)
To
compute for the InDgree of every vertex, O(V+E)
Definitions:
Directed Graph
AdjacencyList
Representation of a Directed Graph
The
outdegree of a vertex is the number of its outedges or number of edges
leaving it. The indgree of a vertex is
the number of its inedges or number of edges entering it.
Demystified Explanation:
To calculate the
out degree of any one, single, vertex, you must go through at most E edges
(where E is the number of edges). So
this is O(E).
To calculate the
out degree of every vertex (all of them), you will still go through at most E
edges, since the total number of edges was E.
But now, you must also iterate once through every vertex...since you
want to look at each of them in turn and count how many edges go out from
them. This iterating through the
vertices is O(V) (where V is the total number of vertices). Putting this together, it gives O(V + E) to
calculate the out degree of every vertex.
Calculating the
indegree will be very similar. Again,
the algorithm would go through every vertex (O(V)) and run through the
adjacency lists (O(E)). For every
vertex it finds inside an adjacency list, it will increment that vertice's
cooresponding indegree count.
Example of the
way tt might run.
Adjacency list:
1>2>3
2>2
3>3
So, starting
with the first vertex, we run through its adjacency list. We find vertices 2 and three, so we
increment their indegree counts to 1.
At the next
vertex, we run through the adjacency list and get vertex 2. We increment its indegree count to become 2
now.
At the third and
last vertex, we run through the adjacency list and get vertex 3. We increment its indegree count to become 2
now.
So we now have the indegree counts of all the vertices (0 for
vertex 1, 2 for vertex 2, and 2 for vertex 3) And again, we've run through
every edge (O(E)), and looked at every vertex (O(V)). So, O(V + E).
PseudoCode Explanation (From a CS Point of
View using Algorithms):
Algorithm for outdegree:
1 For each u in V do
2 outdeg[u] = 0
3 For each u in V do
4 For each v in Adj[u] do
5 outdeg[u] = outdeg[u] + 1 // count #
of edges from u
Time for steps 1 and 2 take
O(V) since there are V vertices.
Steps 3 to 5 take O(max(V,
E)) = O(V + E) time. The reason is that we have to scan through V elements
in array Adj, even if all of them point to NULL. On the other hand, the sum of
the lengths of all adjacency lists is E. We examined each element in
adjacency lists once.
Therefore, O(E + V) +
O(V) = O(E + V)
Algorithm for indegree:
1 For each u in V do
2 indeg[u] = 0
3 For each u in V do
4 For each v in Adj[u] do
5 indeg[v] = indeg[v] + 1 // count # of
edges to v
Steps 1 and 2 take O(V). Steps 3 to 5 take O(max(V, E)) = O(V +
E) time, since we have to scan all the adjacency lists (even if they may be
all empty), and there are V lists. Moreover, the sum of the lengths of all
adjacency lists is O(E). Each element in adjacency lists swill be examined
once.
Therefore, O(E + V) + O(V) = O(E + V)
Give an adjacencylist representation for a complete binary tree on 7 vertices. Give an equivalent adjacencymatrix representation. Assume that the vertices are numbered from 1 to 7 as in a binary heap.
Answer:
Appling the property of binary tree let sketch the vertices: Base on the assumption this is a directed graph
Adjacencylist representation of G:
The equivalent adjacencymatrix representation is as follow:

1 
2 
3 
4 
5 
6 
7 
1 
0 
1 
1 
0 
0 
0 
0 
2 
0 
0 
0 
1 
1 
0 
0 
3 
0 
0 
0 
0 
0 
1 
1 
4 
0 
0 
0 
0 
0 
0 
0 
5 
0 
0 
0 
0 
0 
0 
0 
6 
0 
0 
0 
0 
0 
0 
0 
7 
0 
0 
0 
0 
0 
0 
0 
Exercise 22.13:
The transpose of a directed graph G = (V, E) is the graph G^{T} = (V, E^{T}), where E^{T} = {(v,u) Î V x V : (u, v) Î E}. Thus G^{T} = G with all its edges reversed. Describe efficient algorithms for computing G^{T} from G for both adjacencylist and adjacencymatrix representations of G. Analyze the running time of your algorithms.
Answer:
Figure (A) (figure 22.2 in the textbook) as a directed graph G = (V, E).
Redrawn the graph in reversed order we have figure (B) – adjacencylist and figure (C)  adjacencymatrix.
a) Let create a new adjacencylist Adj_List^{T} and the Adj is the original graph. Building x by transpose the original Adj
Transpose(V, E, Adj)
{
for each v in V
Adj_List^{T}[v].Clear()
for each u in Adj[v]
Adj_List^{T}[u].Insert(v)
return Adj_List^{T}
}
The
running time is O = (V + E).
b) Adj_Matrix^{T} is the transposed of the original adjacencymatrix.
Transpose(V, E, Adj)
{
for i = 1 to V.Size
for j = 1 to V.Size
Adj_Matrix^{T}[j,
i] = Adj[i, j]
return Adj_Matrix^{T}
}
The running time is O = V^{2}^{}
References:
http://www.comp.nus.edu.sg/~stevenha/programming/prog_graph7.html
http://cody.ebberson.com/classes/csce423/hwk2/
Given an adjacencylist representation of a multigraph G = (V, E), describe an O(V + E)time algorithm to compute the adjacencylist representation of the "equivalent" undirected graph G' = (V, E'), where E' consists of the edges in E with all multiple edges between two vertices replaced by a single edge and with all selfloops removed.
Answer:
The answer is going to be similar to the answer in 22.13 (a).