JAVA 图算法实现、代写Graphs 数据结构-代写Algorithm 算法作业

Lab Case – Algorithms and Data Structure, 2017-2018

Phase 3. Graphs

Currently, SharingCar only provides service in ten cities (Madrid, Barcelona,

Valencia, Sevilla, Bilbao, Granada, Toledo, Salamanca, Alicante, Cáceres). Note: you

can ignore the accents.

Every day, SharingCar creates a map with all its travels offered in order to know

the possible connections between cities.

Implement a graph, whose vertices are the cities (you must use an array of String

to store the vertices. In this way, each city is represented by a index from 0 to 9).

Please, take into account that, for example, the offer (Madrid, Barcelona) is not

equal to (Barcelona, Madrid). The class must contain the following methods:

• A constructor method that takes an array of cities and build the basic

structure to create the graph.

• A method, setTravels(LstRequest offers), that takes a list of offers to create

the edges of the graph with the offered travels. For example, if an offer

provides a travel between Madrid (0) and Barcelona (1), the method must

create an edge (with weight equals to 1) between these two vertices. If the

edge already exists, then the method only has to increase its associated

weight. In other words, an edge represents the number of offered travels

from a city to another. Please, explain its time complexity (Big-O function).

• A method, getListDestination(String city), that takes a city and returns all

possible destinations. Please, explain its time complexity (Big-O function).

• A method, getListOrigin(String city), that takes a city and returns all

possible origin to this city. Please, explain its time complexity (Big-O

function).

• A method, getAllCities(), returning all cities in the graph obtained through

a depth traversal.

• A method, nonConnectedCities() that returns a list of cities which are not

connected (there is no path between them). For example, Sevilla is

connected to Barcelona via Toledo and Madrid, but there is no travel from

Barcelona to Sevilla, so (Barcelona, Sevilla) must be part of the returned list.

• Please, explain the space complexity of your data structure.