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.Data structures & Algorithms

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:

Instructions Files

Expert's Answer

OR

Data structures & Algorithms Experts

expert
Leroy Bicknell
Data structures & Algorithms

93 Answers

expert
Owen Charles
Data structures & Algorithms

49 Answers

View More Experts
Disclaimer

The ready solutions purchased from Library are already used solutions. Please do not submit them directly as it may lead to plagiarism. Once paid, the solution file download link will be sent to your provided email. Please either use them for learning purpose or re-write them in your own language. In case if you haven't get the email, do let us know via chat support.

Get Free Quote!

266 Experts Online