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;

      }

Attachments:

Expert's Answer

664 Times Downloaded

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. 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. The LineItem class will represent an individual

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

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of