Here are more details. Suppose we have a graph with 5 vertices and a new vertex Boston comes along. Adjacency information pertaining to Boston would be stored in row 5 and column 5 of the adjacency matrix. Therefore, we would insert the pair (Boston, 5) into a Dictionary object that keeps track of vertex names and their indices. Later, if we want to get the index of the vertex Boston we would search the Dictionary object for Boston. Not only would we find Boston, we would also find the corresponding index 5.
Therefore the tasks you need to complete are:
What to submit: The Link class, LinkList class, the Dictionary class, and the myGraph class. The names of these files should be Link.java, LinkList.java, the Dictionary.java, and myGraph.java. These should all be placed in a directory called homework4 and that is what you should submit. We do not want any other files, we do not want files with other names, and we do not want these files to be submitted separately. We will test your implementation of the myGraph class with the Ladders program from the previous homework.
Some clarifications:
Wikipedia has a nice entry for the trie data structure. To explain what a trie is, let me consider the same example that is presented at wikipedia. You should follow the picture there, as you read this explanation. Suppose that we want to store the words {to, tea, ten, in, inn}. We have one node representing our entire collection, called the root node. This root node has an array of size 26 with one slot in the array for each lower letter. The slot in the array corresponding to character 'a' would point to the collection of all words that begin with 'a'. The slot in the array corresponding to character 'b' would point to the collection of all words that begin with 'b', and so on. In our example, we have no words starting with 'a' and therefore slot in the array corresponding to character 'a' would be null. However, the slots corresponding to characters 'i' and 't' would point to other nodes, that respectively represent all words that start with 'i' and all words that start with 't'. Let us call these, node i and node t respectively. Let me now explain what is stored in node t. Just like the root node, node t also has an array of size 26. Slot 'a' in this array points to all words that start with 'ta', slot 'b' points to all words that start with 'tb', and so on. Since there are no words in our collection that start with 'ta', slot 'a' in node t will have a null. However, slot 'e' in node t will point to another node, called node te, and representing all words in the collection that start with 'te'.