Java程序辅导

C C++ Java Python Processing编程在线培训 程序编写 软件开发 视频讲解

客服在线QQ:2653320439 微信:ittutor Email:itutor@qq.com
wx: cjtutor
QQ: 2653320439

Exercise 1a of this labsheet is worth 2.5% of your final mark in this unit.The final date for submission is: 11:59pm Wednesday, 27 April 2016.

The aims of this labsheet are to:

  1. implement a bredth first search of a graph, and apply it to find distances of vertices from a specified source.

  2. implement a depth first search of a directed graph and apply it to finding the start times and finish times of vertices.

Exercises

Use the Graph, class provided on the unit web-page, to write a breadth-first search algorithm and depth first search algorithm for directed graphs (as described in the lecture notes). The interface Search is provided and you should implement it as a class SearchImp. You should complete the following methods:
  1. The method getConnectedTree should output an array specifying the parent vertex for each vertex (or -1 if there is no parent), assuming a Breadth First Search.
  2. The method getDistances should output an array specifying the distance each vertex is from the starting vertex, or -1 if it is not reachable.
  3. In the method, getTimes you should, assuming a depth first search, output the start and finish times for each vertex. Given that the graph G has n vertices, the method getTimes(G) should return an n × 2 array of integers. For example. if a = getTimes(G) then the start time for vertex i is a[i][0] and the end time for vertex i is a[i][1].
Fully document your code using javadoc comments.

Submit your SearchImp implementation to .

If submitted before the due date, the system will compile and run your code, estimate your mark, and provide you with feedback. Final marking will occur after the posted due date and is subject to further examination, testing, and plagiarism checks of your code. Note that for security reasons, your code cannot contain any I/O commands, including printing statements. Although the auto-marking program provides you with some feedback, it should not be used as a substitute for your own testing.


The University of Western Australia

School of Computer Science and Software Engineering

University information

This Page