traversal of the tree from the root. Rotate p to right. Output in the file f4.txt must be the following:(C,8,2) (D,6,1) (E,9,4) (F,2,-1) (G,7,3) (H,10,8) (1,1,7) (J,3,9) (K,-1,5) (L,5,10) (M,4,6)
(C,8,2) (F,2,-1) (E,9,4) (1,1,7) (D,6,1) (H,10,8) (K,-1,5) (J,3,9) (G,7,3) (L,5,10) (Μ,4,6)
Question 3: (2 marks)
In this question you should complete some methods in Graph.java file.
The class Graph is the implementation of a graph. The following methods should be completed:
void f1() - Perform depth-first traversal (to the file f1.txt) from the vertex i=4 (the vertex E) but display 6 vertices with their degrees from the 2nd vertex to the 7th vertex only. Hint: copy depth(...) to depth2(...) and modify the latter one. The array int deg[] already declared in the class Graph. You should calculate d[i] = degree of the vertex i, i=0,1,..,n-1 and use the function fvisitDeg(...) to display a vertice with degree to file. Content of the output file f1.txt must be:
EBACFHIDG
B(3) A(3) C(3) F(1) H(2) I(1)
void f2() - Apply the Dijkstra's shortest path algorithm to find the shortest path from vertext 0 (A)to vertex 6 (G). Write 3 lines to the file f2.txt: line 1 contains the last 4 vertices selected into the set S, line 2 contains labels of vertices in line 1, line 3 contains the shortest distance, the 1st, 4th and last vertices in shortest path. (Note that in the weighted matrix, the value 99 is considered as infinity. When the vertex v is selected to the set S, its label=shortest distance from starting vertex to it). Output in the file f2.txt must be the following:
DHFG
12 12 17 22
Zoom FUD
Close
22 AEG
+ 127%
