GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1054

C HAPTER S UMMARY
1.

A graph is a useful mathematical structure that represents relationships among entities
in the real world. You learned how to model graphs using classes and interfaces, how to
represent vertices and edges using arrays and linked lists, and how to implement opera-
tions for graphs.

2.

Graph traversal is the process of visiting each vertex in the graph exactly once. You
learned two popular ways for traversing a graph: the depth-first search (DFS) and
breadth-first search (BFS).

3.

DFS and BFS can be used to solve many problems such as detecting whether a graph
is connected, detecting whether there is a cycle in the graph, and finding a shortest path
between two vertices.

Q UIZ

Answer the quiz for this chapter online at www.cs.armstrong.edu/liang/intro10e/quiz.html .

P ROGRAMMING E XERCISES

Sections 28.6-28.10
*28.1

( Test whether a graph is connected ) Write a program that reads a graph from
a file and determines whether the graph is connected. The first line in the file
contains a number that indicates the number of vertices ( n ). The vertices are
labeled as 0 , 1 , . . . , n-1 . Each subsequent line, with the format u v1 v2 ... ,
describes edges ( u , v1 ), ( u , v2 ), and so on. Figure 28.21 gives the examples of
two files for their corresponding graphs.

File
6
0 1 2
1 0 3
2 0 3 4
3 1 2 4 5
4 2 3 5
5 3 4

File
6
0 1 2 3
1 0 3
2 0 3
3 0 1 2
45
54

0 1

0 1

2 3

2 3

4 5 4 5

(a) (b)

F IGURE 28.21

The vertices and edges of a graph can be stored in a file.

Your program should prompt the user to enter the name of the file, then it should
read data from the file, create an instance g of UnweightedGraph , invoke
g.printEdges() to display all edges, and invoke dfs() to obtain an instance
tree of AbstractGraph.Tree . If tree.getNumberOfVerticesFound()
is the same as the number of vertices in the graph, the graph is connected. Here
is a sample run of the program: