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

Enter a file name: c:\exercise\GraphSample1.txt
The number of vertices is 6
Vertex 0: (0, 1) (0, 2)
Vertex 1: (1, 0) (1, 3)
Vertex 2: (2, 0) (2, 3) (2, 4)
Vertex 3: (3, 1) (3, 2) (3, 4) (3, 5)
Vertex 4: (4, 2) (4, 3) (4, 5)
Vertex 5: (5, 3) (5, 4)
The graph is connected

( Hint : Use new UnweightedGraph(list, numberOfVertices) to create
a graph, where list contains a list of AbstractGraph.Edge objects. Use
new AbstractGraph.Edge(u, v) to create an edge. Read the first line to
get the number of vertices. Read each subsequent line into a string s and use
s.split("[\\s+]") to extract the vertices from the string and create edges
from the vertices.)

*28.2

( Create a file for a graph ) Modify Listing 28.1, TestGraph.java, to create a file
representing graph1 . The file format is described in Programming Exercise 28.1.
Create the file from the array defined in lines 8-21 in Listing 28.1. The number
of vertices for the graph is 12 , which will be stored in the first line of the file.
The contents of the file should be as follows:

12
0 1 3 5
1 0 2 3
2 1 3 4 10
3 0 1 2 4 5
4 2 3 5 7 8 10
5 0 3 4 6 7
6 5 7
7 4 5 6 8
8 4 7 9 10 11
9 8 11
10 2 4 8 11
11 8 9 10

*28.3

( Implement DFS using a stack ) The depth-first search algorithm described in
Listing 28.8 uses recursion. Design a new algorithm without using recursion.
Describe it using pseudocode. Implement it by defining a new class named
UnweightedGraphWithNonrecursiveDFS that extends UnweightedGraph
and overriding the dfs method.

*28.4

( Find connected components ) Create a new class named MyGraph as a subclass
of UnweightedGraph that contains a method for finding all connected com-
ponents in a graph with the following header:

public List<List<Integer>> getConnectedComponents();

The method returns a List<List<Integer>> . Each element in the list is
another list that contains all the vertices in a connected component. For exam-
ple, for the graph in Figure 28.21b, getConnectedComponents() returns
[[0, 1, 2, 3], [4, 5]] .