2
void f40 Suppose p is the 2nd node having 2 non-empty children when performing
breadth-first traversal of the tree. 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) (M,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 breadth-first traversal (to the file f1.txt) from the vertex i=1 (the vertex B)
but display 6 vertices from the 2nd vertex to the 7th vertex only. Of these, 3 first vertices displayed
with their degrees. Hint: copy breadth(...) to breadth2(...) 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:
BADECGHFI
A(3) D(3) E(2) CGH
"
void f2()-Apply the Dijkstra's shortest path algorithm to find (1) the shortest path from vertext
0 (A) to vertex 6 (G), then (2) from vertex 2 (C) to vertex 6 (G). Write 3 lines to the file f2.txt: line
1 contains the first 7 vertices selected into the set S in (1), of these, the first 4 vertices displayed
with labels. Line 2 contains vertices in shortest path (1), line 3 contains vertices in shortest path
(2). (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:
A(0) I(2) C(5) E(8) BDH
AICED G
CED G
Zoom
+ 100%
Close
