Chapter 28, Problem 28.1PE

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