《算法习题解答(二)》由会员分享，可在线阅读，更多相关《算法习题解答(二)（4页珍藏版）》请在金锄头文库上搜索。
1、Homework 6 Solutions 1. 22.2-6 (pg. 539) There are two types of professional wrestlers: good guys, and bad guys. Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose that we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are
2、 rivalries. Give an O(n + r)-time algorithm that determines whether it is possible to designate some of the wrestlers as good guys and the remainder as bad guys such that each rivalry is between a good guy and a bad guy. If it is possible to perform such a designation your algorithm should produce i
3、t. Assumptions: 1. A rivalry (A, B) represents the fact that A has a rivalry with B. It does not specify whether or not A or B is the good or bad guy. 2. Some wrestlers may not be involved in rivalries. These wrestlers are neither good guys nor bad guys. The algorithm is not concerned with them. 3.
4、Any possible solution of good guys and bad guys is acceptable. For example, consider the following setup: Wrestlers = A, B, C, D, E, Rivalries = (A, B), (B, C), (D, E) There are four possible solutions for this set up: 1. Good guys = A, C, D, Bad guys = B, E 2. Good guys = A, C, E, Bad guys = (B, D
5、3. Good guys = B, E, Bad guys = A, C, D 4. Good guys = B, D, Bad guys = A, C, E An correct algorithm could return any one of these solutions. Setup: We represent the rivalries as a graph, G = (V, E). The vertices are the wrestlers, and the edges are the rivalries. Therefore, |V| = n, and |E| = r. Al
6、gorithm: 1. Discard all vertices of degree 0. These are wrestlers who have no rivalries. We are not concerned with them. 2. Separate all connected components of the remaining graph. Process each component individually in the following steps. 3. Let C = (Vc, Ec) be the connected component. Choose one
7、 vertex r at random (or deterministically-it doesnt matter) from Vc. Without loss of generality (remember, any possible solution, is correct), let r be classified as a Good guy. 4. Run a modified breadth-first search from the root. Instead of maintaining d and f arrays, save the path-length from eac
8、h vertex to r. All vertices with odd path lengths to r are Bad guys; all vertices with even path lengths to r are Good guys. 5. Examine every edge in Ec. If the edge is between two vertices whose path lengths to r are both even or both odd, then we have established a rivalry between two Good or Bad
9、guys. If this is the case, we return false it is not possible to partition the wrestlers. 6. If we are able to examine every edge in every connected component without returning false, then we have successfully partitioned the wrestlers in step 4. Complexity: The major time-related component of this
10、algorithm is the breadth- first search, which has O(V + E) time. 2. 22.2-8 (pg. 539) Let G = (V, E) be a connected, undirected graph. Give an O(V + E)-time algorithm to compute a path in G that traverses each edge in E exactly once in each direction. Describe how you can find your way out of a maze
11、if you are given a large supply of pennies. To solve this problem, we use a variant of depth-first search. Every edge is marked the first and second time it is traversed with unique marks for each traversal. Edges that have been traversed twice may not be taken again. Our depth-first search algorith
12、m must ensure that all edges all explored, and that each edge is taken in both directions. To ensure that all edges are explored, the algorithm must ensure that unexplored edges are always taken before edges that are explored once. To ensure that edges are taken in each direction, we simply backtrac
13、k every time the depth-first search reaches a dead-end. The search keeps backtracking until a new unexplored edge is found. This way, edges are only explored in the reverse direction during the backtracking. Complexity: This algorithm is based on depth-first search, which has time complexity O(V+ E)
14、. 3. 2.3-4 (pg. 548) a.) Show that edge (u, v) is a tree edge or forward edge if and only if du dv. Similarly, we cannot have du fv, because this would indicate that v was finished (but not discovered) after u was discovered, but before u was finished, which cannot happen. Therefore, dv fv du fu ?:
15、Assume dv fv du fu. Since fv du, there is no parental or ancestral relationship between u and v. Therefore edge (u, v) is a cross edge. 4. 22.3-8 (pg. 548) Give a counterexample to the conjecture that if there is a path from u to v in a directed graph G, then any depth-first search must result in dv
16、 fu. d f s 1 6 u 4 5 v 2 3 vu s We perform a DFS starting at vertex s. We then discover vertex u. Since the only edge out of u is (u, s), and s has been found, we finish u. Next, we discover and finish v. Finally, we finish s. 5. 22.4-2 (pg. 552) Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of paths from s to t in G. The basic idea here is to
