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. The figure below gives examples of two files and their corresponding graphs.
The graph: see image.
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.
Create the data files to represent the graphs created as part of the Analysis & Design for this assignment. Run your program using the files you created and the provided files.
Provided Files graph1.txt graph2.txt graph3.txt city-graph.txt
Here is a sample run of the program:
Enter a file name: GraphSample1.txt
The number of vertices is 4
Vertex 0: (0, 1) (0, 2) (0, 3)
Vertex 1: (1, 0) (1, 3)
Vertex 2: (2, 0) (2, 3)
Vertex 3: (3, 0) (3, 1) (3, 2)
The graph is not connected
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.
graph1.txt
6
0 1 2 3
1 0 3
2 0 3
3 0 1 2
4 5
5 4
graph2.txt
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
graph3.txt
8
0 1 7
1 4 5
2 5 6
3 6 7
4 0 1
5 1 2
6 2 3
7 3 0