CS341 : hw3ans.pdf
Document Summary
22. 1-2 give an adjacency-list representation for a complete binary tree on 7 vertices. Assume that vertices are numbered from 1 to 7 as in a binary heap. G2 for an adjacency matrix: - computing g2 may be done in v3 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) { V[g2] v[g] for each u v[g] Run time = o(v3) for each v adj[u] for each w adj[v] E[g2] {(u, w)} e[g2: 22. 2-1 show the d and values that result from running breadth-first search on the directed graph of figure 22. 2(a), using vertex 3 as the source. Each vertex can be explored once and its adjacent vertices must be determined too. (v2) time: do a dfs on figure 22. 6 (p. 548). Classify each edge based on the dfs tree you determine.
