JAVA 图算法实现、辅导Graphs 数据结构
解析C/C++编程|辅导Database
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.