
Concept explainers
Test whether a graph is connected
Program Plan:
Exercise.java:
- Import the required packages.
- Create a class “Exercise”:
- Define the main method
- Prompt user to enter the link.
- Get the input
- The input is validated to read the number of vertices present in the graph.
- Display the count of the vertices.
- New array list gets defined.
- Loop that iterates to validate the input and remove the tokens.
- The graph values are validating by performing a depth first search.
- Condition to validate the vertices of the graph.
- Display the graph is connected or not connected.
- Define the main method
UnweightedGraph.java:
- Import the required packages.
- Create a class “UnweightedGraph”:
- New list for the vertices gets created.
- New list for the neighbor node gets created.
- Create an empty constructor.
- Method to create new graph gets created and adjacency list gets created.
- Method to create an adjacency list gets created.
- Method to return the size of the vertices.
- Method to return the index of the vertices gets defined.
- Method to gets the neighbor node gets defined.
- Method to return the degree of the vertices gets created.
- Method to print the Edges gets created.
- New to clear the graph gets created.
- Method to add vertex gets created.
- Method to add edge gets created.
- Method to perform the depth first search gets defined.
- Method to perform breadth first search gets defined.
- Search tree gets returned.
- Create a class “SearchTree”,
- Define the method to return the root.
- Method to return the parent of the vertices
- Method to return the search order gets defined.
- Method to return the number of vertices found gets defined.
- Method to get the path of the vertices gets defined.
- Loop to validate the path gets defined.
- Path gets returned.
- Method to print the path gets defined.
- Method to print the tree gets defined.
- Display the edge.
- Display the root.
- Condition to validate the parent node to display the vertices gets created.
Graph.java:
- A graph interface gets created.
- Method to return the size gets defined.
- Method to return the vertices gets defined.
- Method to return the index gets created.
- Method to get the neighbor node gets created.
- Method to get the degree gets created.
- Method to print the edges.
- Method to clear the node gets created.
- Method to add the edges, add vertex gets created.
- Method to remove the vertices gets defined.
- Method for the depth first search gets defined.
- Method for the breadth first search gets defined.
Edge.java
- Create a class “Edge”,
- Define and declare the required variables.
- Constructor gets defined.
- Method that defines Boolean objects gets defined.
- Return the value after validating the vertices.

The below program is used to test whether the graph given is connected or not
Explanation of Solution
Program:
Exercise.java:
//import the required headers
import java.util.*;
//define the class exercise
public class Exercise
{
//main method
public static void main(String[] args) throws Exception
{
//scanner input gets defined
java.util.Scanner input = new java.util.Scanner(System.in);
//prompt user to enter the link
System.out.print("Enter a URL: ");
//get the link
java.net.URL url = new java.net.URL(input.nextLine());
//method to open the url
java.util.Scanner inFile = new java.util.Scanner(url.openStream());
//number of vertices are read
String s = inFile.nextLine();
//get the number of vertices
int ver_num = Integer.parseInt(s);
//display the count of vertices
System.out.println("The number of vertices is "
+ ver_num);
//new array list gets defined
java.util.List<Edge> list = new java.util.ArrayList<>();
//loop that validate the file
while (inFile.hasNext())
{
//read the file
s = inFile.nextLine();
//key words are read
String[] tokens = s.split("[\\s+]");
//read the starting vertex
int startingVertex = Integer.parseInt(tokens[0].trim());
/*loop that iterates for the entire length of the file*/
for (int i = 1; i < tokens.length; i++)
{
//remove the tokens
int adjacentVertex = Integer.parseInt(tokens[i].trim());
//add integers to the list
list.add(new Edge(startingVertex, adjacentVertex));
}
}
//new graph gets defined
Graph<Integer> mygraph = new UnweightedGraph<>(list, ver_num);
//display the edges
mygraph.printEdges();
//perform depth first serach
UnweightedGraph<Integer>.SearchTree mytree = mygraph.dfs(0);
//condition to validate the vertices
if (mytree.getNumberOfVerticesFound() == ver_num)
//display the graph is connected
System.out.println("The graph is connected");
else
//display the graph is not connected
System.out.println("The graph is not connected");
}
}
UnweightedGraph.java: Refer Listing 28.4 in the textbook.
Graph.java: refer Listing 28.3 in the textbook.
Edge.java: refer Listing 28.1 in the textbook.
Enter a URL:
http://liveexample.pearsoncmg.com/test/GraphSample1.txt
The number of vertices is 6
0 (0): (0, 1) (0, 2)
1 (1): (1, 0) (1, 3)
2 (2): (2, 0) (2, 3) (2, 4)
3 (3): (3, 1) (3, 2) (3, 4) (3, 5)
4 (4): (4, 2) (4, 3) (4, 5)
5 (5): (5, 3) (5, 4)
The graph is connected
Want to see more full solutions like this?
Chapter 28 Solutions
Introduction to Java Programming and Data Structures, Comprehensive Version, Student Value Edition (11th Edition)
- 1. Transform the E-R diagram into a set of relations. Country_of Agent ID Agent H Holds Is_Reponsible_for Consignment Number $ Value May Contain Consignment Transports Container Destination Ф R Goes Off Container Number Size Vessel Voyage Registry Vessel ID Voyage_ID Tonnagearrow_forwardI want to solve 13.2 using matlab please helparrow_forwarda) Show a possible trace of the OSPF algorithm for computing the routing table in Router 2 forthis network.b) Show the messages used by RIP to compute routing tables.arrow_forward
- using r language to answer question 4 Question 4: Obtain a 95% standard normal bootstrap confidence interval, a 95% basic bootstrap confidence interval, and a percentile confidence interval for the ρb12 in Question 3.arrow_forwardusing r language to answer question 4. Question 4: Obtain a 95% standard normal bootstrap confidence interval, a 95% basic bootstrap confidence interval, and a percentile confidence interval for the ρb12 in Question 3.arrow_forwardusing r languagearrow_forward
- using r languagearrow_forwardusing r language Obtain a bootstrap t confidence interval estimate for the correlation statistic in Example 8.2 (law data in bootstrap).arrow_forwardusing r language Compute a jackknife estimate of the bias and the standard error of the correlation statistic in Example 8.2.arrow_forward
- using r languagearrow_forwardusing r languagearrow_forwardThe assignment here is to write an app using a database named CIT321 with a collection named students; we will provide a CSV file of the data. You need to use Vue.js to display 2 pages. You should know that this assignment is similar, all too similar in fact, to the cars4sale2 example in the lecture notes for Vue.js 2. You should study that program first. If you figure out cars4sale2, then program 6 will be extremely straightforward. It is not my intent do drop a ton of new material here in the last few days of class. The database contains 51 documents. The first rows of the CSV file look like this: sid last_name 1 Astaire first_name Humphrey CIT major hrs_attempted gpa_points 10 34 2 Bacall Katharine EET 40 128 3 Bergman Bette EET 42 97 4 Bogart Cary CIT 11 33 5 Brando James WEB 59 183 6 Cagney Marlon CIT 13 40 GPA is calculated as gpa_points divided by hrs_attempted. GPA points would have been arrived at by adding 4 points for each credit hour of A, 3 points for each credit hour of…arrow_forward
- C++ Programming: From Problem Analysis to Program...Computer ScienceISBN:9781337102087Author:D. S. MalikPublisher:Cengage LearningC++ for Engineers and ScientistsComputer ScienceISBN:9781133187844Author:Bronson, Gary J.Publisher:Course Technology PtrSystems ArchitectureComputer ScienceISBN:9781305080195Author:Stephen D. BurdPublisher:Cengage Learning
- Programming Logic & Design ComprehensiveComputer ScienceISBN:9781337669405Author:FARRELLPublisher:CengageMicrosoft Visual C#Computer ScienceISBN:9781337102100Author:Joyce, Farrell.Publisher:Cengage Learning,EBK JAVA PROGRAMMINGComputer ScienceISBN:9781337671385Author:FARRELLPublisher:CENGAGE LEARNING - CONSIGNMENT




