Due – November 7, 2019, 6:00 PM, at the class beginning
All work must be your own. Upload copy of your homework and any supporting materials
(source code and test cases) online to Assignment5 in the CS566_A2 course site
No extensions or late submissions for anything other than major emergency. Show your work
Q1 [15 pts.]: Find the depth-first search tree for the graph Fig.1 with G as the starting vertex.
Assume that each adjacency list is in alphabetical order.
Q2 [15 pts.]: Find the breadth-first search tree for the graph Fig.1 with G as the starting vertex.
Assume that each adjacency list is in reverse alphabetical order
Q3 [25 pts.]: Execute Prim’s minimum spanning tree algorithm by hand on the graph in Fig.2,
showing how the data structures evolve. Clearly indicate which edge s become part of
minimum spanning tree and in what order. Start at vertex H.
Q4 [25 pts.]: Dijkstra’s shortest path algorithm.
Here are the adjacency list with edge weights in parentheses for a digraph Fig.3
A: B (4.0), F (2.0)
B: A (1.0), C (3.0), D (4.0)
C: A (6.0), B(3.0), D(7.0)
D: A (6.0), E(2.0)
E: D (5.0)
F: D(2.0), E(3.0)
Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data
structures evolve, with s = A. Clearly indicate which edge become part of the shortest –
path tree in what order.
Q5 [20 pts.]: [Kruskal’s minimum spanning tree algorithm]
Find the minimum spanning tree for the graph in Fig.4 that would be the output by Kruscal’s
algorithm, assuming that edges are sorted as shown on Fig.4
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:dmxyzl003