A graph is a weighted graph if each edge is assigned a weight. Weighted graphs have many practical applications.
Figure above assumes that the graph represents the number of flights among cities. You can apply the BFS to find the fewest number of flights between two cities. Assume that the edges represent the driving distances among the cities as shown in Figure below. How do you find the minimal total distances for connecting all cities? How do you find the shortest path between two cities? This chapter will address these questions. The former is known as the minimum spanning tree (MST) problem and the latter as the shortest path problem.
The preceding chapter introduced the concept of graphs. You learned how to represent edges using edge arrays, edge lists, adjacency matrices, and adjacency lists, and how to model a graph using the Graph interface, the AbstractGraph class, and the UnweightedGraph class. The preceding chapter also introduced two important techniques for traversing graphs: depth-first search and breadth-first search, and applied traversal to solve practical problems. The following posts will introduce weighted graphs. You will learn the algorithm for finding a minimum spanning tree in post and the algorithm for finding shortest paths in post .
Top comments (0)