代写C++ DFS 数据结构、代写DFS C++实现

日期：2018-04-25 02:15

Please note that you have to typeset your assignment using either LATEX or Microsoft

Word, and produce a PDF file for submission. Hand-written assignment (or photo of

it) will not be graded. You need to submit an electronic version (in PDF form) on the

blackboard. You should name your file using the format CSE310-HW05-LastNameFirstName.

1. (20 points) Figure 1 shows a directed graph G. Assume that the adjacency list lists the

edges in alphabetical order.

B E

C F

A D G H

Figure 1: Graph for P1.

(a) Apply depth first search (DFS) to graph G, and show the discovery and finish times

of each vertex. In the main-loop of DFS, check the vertices in alphabetical

order. You can write the results on the graph in Figure 1.

(b) Draw the DFS tree obtained.

(c) Draw the transpose graph GT of the graph in Figure 1. The vertices are given for your

convenience.

B E

C F

A D G H

1

(d) Apply DFS to GT

to compute the strongly connected components. You need to show

the strongly connected components and indicate the order they are computed.

2. (10 points) This problem assumes an undirected graph obtained by ignoring the directions

of the graph in Figure 1. Assume that we perform breadth first search (BFS) on this graph,

starting at vertex A.

(a) Show the set of vertices L0, L1, L2, L3.

(b) Draw the resulting BFS tree.

3. (10 points) You are given two sequences X = AST U and Y = ASUT Z. Use dynamic

programming to compute the LCS of X and Y .

(a) Fill out the 20 entries in the following table. For each of the entries, you need to show

both the value and the arrow.

j 0 1 2 3 4 5

i A S U T Z

0 0 0 0 0 0 0

1 A 0

2 S 0

3 T 0

4 U 0

(b) What is the LCS computed according to the table?

4. (10 points) We want to use dynamic programming to compute the optimal ordering for computing

the chain of 6 matrices: A1A2A3A4A5A6, where Ai has pi−1 rows and pi columns.

Suppose that p0 = 10, p1 = 5, p2 = 20, p3 = 6, p4 = 30, p5 = 7, p6 = 100.

(a) Compute the entries m[i, j] and s[i, j] as shown in the lecture slides.

(b) Add parenthesise to show the optimal ordering.

2