You start this program by reading the user word into a BST, you hold on to your BST object, in case at any point the user chose option 1 which is to display this tree as a visual tree.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Download the code provided by the textbook in order to complete this program.

We all know by now that any acyclic graph can be considered a tree. Write a program that "maps" a BST to a Graph.

In previous assignments you have read a word (a String) from the keyboard, dissected it into its single letters and configured these letters into a Binary Search Tree. (The word will be all in Caps.)

You are going to start with the same process here. But then you will take your BST and store it in a Graph. This means that you should visit every node in the BST and not only store that as a vertex in the array that represents the Graph, but also populate the adjacency matrix based on the parent-child relationship that you detect in your BST.

Another important note here is that the order of the vertices in the vertex array does not tell us anything about the connectivity of these vertices. It’s all about the adjacent matrix that determines the connectivity pattern of this graph. However, we need to know what character is stored in which index, when referring to them, but who they are connected to depends on the data in the adjacency matrix.

Add the following methods to the code given in the textbook:

displayAdjMatrix()

displayVertexList()

Also a method for option 6.

We are going to let the user decide whether they want this to be a DIRECTED or UNDIRECTED graph. So the first question to the user after reading the word would be the following:

Map the BST into:

1. Directed Graph.
2. Undirected Graph.

After the following input from the user, you map the BST into the proper Graph, and then you will display a menu and let the user choose from the following options:

1. Display the BST in a tree format.
2. Display the Vertex array.
3. Display the Adjacency Matrix.
4. Display the result of Depth-First-Search starting on specific vertex:

1. Enter the letter.
   5. Display the result of Breadth-First-Search starting on specific vertex:
2. Enter the letter.
   6. Display the vertices that are direct neighbors (one-edge apart) of a certain vertex.
3. Enter the letter.
   7. (BONUS) Display the vertices that are two edges apart from a certain vertex.
4. Enter the vertex character attribute. (The letter in the input word) 8. Exit.

A Very Important Note: You start this program by reading the user word into a BST, you hold on to your BST object, in case at any point the user chose option 1 which is to display this tree as a visual tree. But any other operations stated as all but option 1, MUST BE DONE ON GRAPH VERSION OF THIS TREE. For example in order to find the one edge away neighbor of a vertex YOU CANNOT TRAVERSE THE BST, YOU SHOULD USE THE ADJACENCY MATRIX.

PLEASE BE ADVISED THAT ANY TREE OPERATION IS GOING TO BE CONSIDERED VOID FOR THIS PROBLEM. THIS IS NOT A TREE PROGRAM!

Option 1. You have already done this in the previous assignments.
Options 2 and 3. You should modify the code in the book so that you define methods for

these options and call them respectively here.

Options 4 and 5. You should modify the code in the book so that you can specify the index of the vertex you would like to choose as starting point. Currently the code starts at index 0 (hard coded for this value.) you need to change that. Please note that the user inputs a letter. You need include the validation code to check to see whether the letter inputted is indeed part of the graph or not.

Option 6. Define a method for this option.

Option 7. This is an opportunity to earn BONUS points. I strongly recommend that you complete this option as well.

Option 8. The user needs to get a chance to choose options as many times as they choose until they choose this option which is the EXIT option.

• -  The program must be written in Java.

 

// bfs.java

// demonstrates breadth-first search

// to run this program: C>java BFSApp

////////////////////////////////////////////////////////////////

class Queue

   {

   private final int SIZE = 20;

   private int[] queArray;

   private int front;

   private int rear;

// -------------------------------------------------------------

   public Queue()            // constructor

      {

      queArray = new int[SIZE];

      front = 0;

      rear = -1;

      }

// -------------------------------------------------------------

   public void insert(int j) // put item at rear of queue

      {

      if(rear == SIZE-1)

         rear = -1;

      queArray[++rear] = j;

      }

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme