Chapter 28, Problem 28.1PE

Question

Want to see more full solutions like this?

Answer 1

Question

Chapter 28, Problem 28.1PE

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Students have asked these similar questions

I need assistance in the series of questions. If you could please answer 1B part of this please that would be amazing. Thank you so much and if you could be deatiled in the explanation as well as the MatLAB Code if needed! Thank you so much

I need assistance in the series of questions. If you could please answer 1C part of this please that would be amazing. Thank you so much and if you could be deatiled in the explanation as well as the MatLAB Code if needed! Thank you so much

I need assistance in the series of questions. If you could please answer 1A of this please that would be amazing. Thank you so much and if you could be deatiled in the explanation as well as the MatLAB Code if needed! Thank you so much

Answer 2

Question

Chapter 28, Problem 28.1PE

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 3

Question

Chapter 28, Problem 28.1PE

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 4

Question

Chapter 28, Problem 28.1PE

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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?

Subscribe now to access step-by-step solutions to millions of textbook problems written by subject matter experts!

Answer 5

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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

Answer 6

Expert Solution & Answer

Program Plan Intro

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.

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.

Program Description Answer

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.

Sample Output

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

Answer 7

Expert Solution & Answer

Answer 8

Expert Solution & Answer

Answer 9

Program Plan Intro

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.

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.

Answer 10

Program Description Answer

The below program is used to test whether the graph given is connected or not

Answer 11

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.

Answer 12

Sample Output

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

Answer 13

Chapter 28.2, Problem 28.2.1CP Chapter 28.2, Problem 28.2.2CP Chapter 28.2, Problem 28.2.3CP Chapter 28.2, Problem 28.2.4CP Chapter 28.3, Problem 28.3.1CP Chapter 28.3, Problem 28.3.2CP Chapter 28.4, Problem 28.4.1CP Chapter 28.4, Problem 28.4.2CP Chapter 28.4, Problem 28.4.3CP Chapter 28.4, Problem 28.4.4CP

Chapter 28, Problem 28.1PE

Concept explainers

Explanation of Solution

Want to see more full solutions like this?

Chapter 28 Solutions