☑Kizspy.me
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=0 (the vertex A) 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:
ABD GEHICF
B(3) D(3) G(1) E(2) H(2) I(1)
"
void f2() Apply the Dijkstra's shortest path algorithm to find (1) the shortest path from vertext
0 (A) to vertex 5 (F), then (2) from vertex 1 (B) to vertex 6 (G). Write 3 lines to the file f2.txt: line
1 contains vertices in shortest path (1), in which the last vertex (F) having label. Line 2 contains
the last 5 vertices selected into the set S in (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:
AICED F(17)
EBDHF
BC EDG
Zoom
+ 102%
Close
