Assignment 6 (85 points)
CS 610 Spring 2019
Due : Apr.24,2019 in class
Problem 1. (7 points)
How will you modify the DFS biconnectivity algorithm discussed in class so
that we can output edges of each biconnected component ?
Hint: Keep both tree and back edges on stack and think about when to pop
them from stack as part of a biconnected component.
Problem 2. (15 points)
Apply the biconnectivity algorithm discussed in class to the undirected graph
shown in Figure 6.8 of the text book to identify the separation vertices. Your
search should start from vertex A. Assume the adjacent list of each vertex
contains vertices in alphabetical order. For example for vertex M, the adjacency
list has vertices A, B and C in that order. You need to show the DFS tree
showing both tree and back edges and also DF, LOW values for each vertex.
Problem 3. (10 points)
For the following weighted graph, produce minimimum cost spanning tree
(MST) using Prim-Jarn`?k’s algorithm showing all intermediate steps. Your
algorithm should start from vertex a.
1
Problem 4. (10 points)
Repeat the above problem except that you need to use Kruskal’s algorithm for
MST.
2
Problem 5. (10 points)
(a) Show how to modify Dijkstra’s algorithm to not only output the distance
from a vertex s to each vertex in G but also to output a spanning tree
T rooted at s such that the path in T from s to a vertex u is actually a
shortest path in G from v to u. Your output of the tree should be some
thing like ”v1 has shortest distance d and v2 is parent of v1 ”. (5 points)
(b) Do additional modification so that if there are more than one shortest path
from s to u, we output the one with shortest number of edges.(5 points)
Problem 6. (18 points)
Let G = (V, E) be a directed graph where each edge has a probability value
associated with it given by the function p : E? > [0, 1]. Assume there are no
self-cycles in this graph. The reliability of a directed path P = (e1, e2, ...ek)
from vertex u to vertex v given by R(P) = Qk
i=1 p(ei) is the product of probabilities

CS 610留学生作业代做、代写DFS algorithm作业、代做Java
of edges in the path. All-pairs Max Reliablity Problem is one of finding
for each pair of vertices u and v, the maximum reliability among all paths from
u to v.
(a) Define a proper closed semi-ring for this all-pairs problem and prove it is a
closed semi-ring.(7 pts)
(b) Modify Warshall-Floyd algorithm to solve this problem using proper semiring
operations.Your algorithm should also find for each pair of vertices the
actual path that achieves maximum reliability.(8 pts)
(c) Estimate the time complexity of this algorithm specifying exactly the primitive
operations being measured.(3 pts)
Problem 7. (15 points) Problem R-8.4 from the text book. Show all the
different steps of the algorithm and also the miniumum cut.

因为专业，所以值得信赖。如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 

微信：codinghelp