Graphs are useful in modeling and solving real-world problems. For example, the problem to find the least number of flights between two cities can be modeled using a graph, where the vertices represent cities and the edges represent the flights between two adjacent cities, as shown in Figure 28.1. The problem of finding the minimal number of connecting flights between two cities is reduced to finding a shortest path between two vertices in a graph.

Set up a graph data structure in Java to represent the flight routes between the cities

on how to do the following graph traversals, implement the algorithms in Java:

depth-first traversal

breadth-first traversal

the cities:

Seattle (0) San Francisco (1) Los Angeles (2) Dallas (10) Houston (11) Atlanta (8) New York (7) Boston (6) Chicago (5) Denver (3) Kansas City (4) Miami (9)