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?
out-degree : O(E)
in-degree : O(E+V)
Give an adjacency-list representation for a complete binary tree on 7 vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from 1 to 7 as in a binary heap.
| ~ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 6 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 7 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
The transpose of a directed graph G = (V, E) is the graph GT = (V, ET), where ET = {(v, u) in V × V : (u, v) in E}. Thus, GT is G with all its edges reversed. Describe efficient algorithms for computing GT from G, for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
T means transpose.
-
adjacency-list : 遍历所有的节点,对某个节点i,遍历其Adj,将i这个节点增加到Adj中遇到的每个点的Adj中. 需要的时间是O(V+E).
Iterate all the nodes, for each node i, mark its adjacency-list as L, then add i to all the nodes in L. -
adjacency-matrix : 只需要将矩阵转置,需要的时间是O(V*V)
Just transpose the matrix
Given an adjacency-list representation of a multigraph G = (V, E), describe an O(V + E)-time algorithm to compute the adjacency-list 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 self-loops removed.
- We iterate through all the vertices in the multigraph.
- For each of the vertices we iterate through their multigraph adjacency list.
- While iterating through the multigraph adjacency list of a vertex u, we add the neighbor to the new adjacency list of u and u to the new adjacency list of the neighbor, if the neighbor is not vertex u itself and if the neighbor is not already present in the new adjacency list of u.
- The new adjacency list array is a representation of the required undirected graph.
The square of a directed graph G=(V,E) is the graph G2 =(V,E2) such that (u,w) in E2 if and only if for some v in V, both(u,v) in E and(v,w) in E.That is,G2 contains an edge between u and w whenever G contains a path with exactly two edges between u and w. Describe efficient algorithms for computing G2 from G for both the adjacency-list and adjacency-matrix representations of G. Analyze the running times of your algorithms.
G2 for an adjacency matrix: - Computing G2 may be done in O(V^3) time by matrix multiplication:
for i = 1 to V
for j = 1 to V {
G2[i][j] = 0;
for k = 1 to V
if (g[i][k] == 1 && g[k][j] == 1) {
G2[i][j] == 1;
break;
}
}G2 for an adjacency list:
Procedure G-Square (V[G], E[G])
V[G2] <- V[G]
for each u ∈ V[G]
for each v ∈ Adj[u]
for each w ∈ Adj[v]
E[G2] <- {(u, w)} ∪ E[G2]Run time = O(V^3)
When an adjacency-matrix representation is used, most graph algorithms require time Ω(V2), but there are some exceptions. Show that determining whether a directed graph G contains a universal sink-a vertex with in-degree |V| - 1 and out-degree 0-can be determined in time O(V), given an adjacency matrix for G.
从Matrix[1,1]开始,如果当前位置是0,则往右走一步;如果是1,则往下走一步;一直走到最后一行或者最后一列再停下.再检查该位置是否满足universal sink的定义.
If vertex i is a universal sink according to the definition, the i-th row of the adjacency-matrix will be all “0”, and the i-th column will be all “1” except the aii entry, and clearly there is only one such vertex. We then describe an algorithm to find out if a universal sink really exist.
Starts from a11. If current entry aij = 0 then j = j + 1 (take one step right); if aij = 1 then i = i +1 (take one step down). In this way, it will stop at an entry akn of the last row or ank of the last column (n = |V|, 1 ≦ k ≦|V|). Check if vertex k satisfies the definition of universal sink (check for kth row to contain V zeros and kth column to contain k-1 1s, because the column in adajacency matrix defines in degree of a vertex), if yes then we found it, if no then there is no universal sink. Since we always make a step right or down, and checking if a vertex is a universal sink can be done in O(V), the total running time is O(V).
If there is no universal sink, this algorithm won’t return any vertex. If there is a universal sink u, the path starts from a11 will definitely meet u-th column or u-th row at some entry. Once it’s on track, it can’t get out of the track and will finally stop at the right entry.
The incidence matrix of a directed graph G = (V, E) is a |V| × |E| matrix B = (bij) such that
-1 if edge j leaves vertex i
bij = 1 if edge j enters vertex i
0 otherwiseDescribe what the entries of the matrix product B BT represent, where BT is the transpose of B.
T means transpose
Assume we have a simple graph with 3 vertex {X,Y,Z} and two edges{X->Y,X->Z}.
The incidence matrix B for the above graph is as follows.
XY XZ
X -1 -1
B = Y 1 0
Z 0 1The matrix BT is as follows.
X Y Z
BT = XY -1 1 0
XZ -1 0 1The matrix product BBT is as follows.
X Y Z
X 2 -1 -1
BBT = Y -1 1 0
Z -1 0 1
BBT(u,v) = degree of u = indegree + outdegree if u = v
−(number of edges connecting u and v) if u != vSuppose that instead of a linked list, each array entry Adj[u] is a hash table containing the vertices v for which (u, v) in E. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table?
I think the expected time is O(1), because I just go Hashtable t = Adj[u], then return t.get(v);
I think the disadvantage is that Hashtable will take more spaces then linked list.
It could be a binary search tree.
In an adjacency matrix, each vertex is followed by an array of V elements. This O(V)-space cost leads to fast (O(1)-time) searching of edges.
In an adjacency list, each vertex is followed by a list, which contains only the n adjacent vertices. This space-efficient way leads to slow searching (O(n)).
A hash table is a compromise between the array and the list. It uses less space than V, but requires the handle of collisions in searching.
A binary search tree is another compromise -- the space cost is minimum as that of lists, and the time cost in searching is O(lg n).
Disadvantage for BST could be that search/insert/delete operations all need O(lgn) time, while those operations for hash table is O(1) time.
Follow @louis1992 on github to help finish this task.