2023年11月25日

Java代写 | CS566 Homework-5

本次Java代写是实现图的数据结构和寻路算法等

CS566 Homework-5
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
in detail.
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.
Fig.1
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.
Fig.2
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.
Fig.3
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
Fig.4