Representing relations in wordlist by adjacency list for quick search

52 views Asked by At

I am writing a program that is supposed to read a file of words and then find the shortest from one word to another by going from the startword to an adjacent word that will differ with one letter, simple example: Startword: dog endword: for could be: " dog -> fog -> for".

My idea is to do a BFS in a adjacent list. Everything is working in my code except for my Graph (adjacent list). The problem is that I want to hash the words to an index in the graph, but for that the endsize of the list needs to be known.

I start by adding a vector which will contain the entire wordlist, I use the size of this vector to set size of arraylist and then I iterate the vector to hash the words into the arraylist.

My adjacent list is of type:

    ArrayList<LinkedList<String>> adj_list;

Here's how I use it:

    public void adda(Vector<String> v){
    M = v.size();
    adj_list = new ArrayList<LinkedList<String>>(M);
    for (int i = 0; i < M; i++){
        add(v.get(i));
    }

    void add (String word){
    int z = hash(word);
    for (int i = z; i < M; i++){
        if(adj_list.get(i)== null){
            z=i;
            adj_list.add(new LinkedList<String>());
            break;

Hashfunction:

   public static int hash(String key) {
        int i;
        int v = 0;
        for (i = 0; i < key.length(); i++) {
            v += key.charAt(i);
        }
        return v % M;

I have a strong feeling that just the idea of adding a vector to take the elements from it and add to an arraylist is stupid enough. I cannot come up with any better, working, ideas though (and the one I have right now isn't working either). Should I use an adjacency list at all? Is it a good idea to hash the words or are there any better ways? Does anyone sort of understand what type of program I am trying to create and have any idea that might be helpful?

0

There are 0 answers