#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0

    Need some help on BST


    im trying to do a wordladder whereby it takes in graph,vertex,adjlistnode and the main class. However im facing some difficulty on implementing the BFS where it will find a path from one word to another word...
    For eg:
    dog->cat

    from my understanding i have created and add them into my adjlist as well as found the neighbour for each words in my dictionary.
    for eg: (parent)fine : (neighbour)line|five
    Now im facing some problems with the BFT...
    How do i proceed from here and add it to the queue? predecessor,visited?
  2. #2
  3. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Can you make a small, complete program that compiles, executes and shows the problem?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0
    Originally Posted by NormR
    Can you make a small, complete program that compiles, executes and shows the problem?

    Yes for eg, i have a dict file that contains words like fine,line,dime,rime,lime,five and from there the current program im able to generate out is this output which is to find the neighbour of each words with 1 character word difference...

    so here goes..
    fine : |line|five|
    line : |fine|lime|
    dime : |rime|lime|
    rime : |dime|lime|
    lime : |line|dime|rime|
    five : |fine|

    base on this, how am i able to construct a Breath First Search to to find a path using the start word and end word?
  6. #4
  7. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Are you asking for an algorithm for solving this problem?
    Or do you have an algorithm and are having problems coding it in java?
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0
    Originally Posted by NormR
    Are you asking for an algorithm for solving this problem?
    Or do you have an algorithm and are having problems coding it in java?
    The alogorithm i have to use is Breath first search..
    and im having problems coding that in java..
  10. #6
  11. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Ok, which step in the algorithm are you having problems coding?
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0
    Like wad i mentioned i have threw every thing into an linked list and can successfully display it's neighbour words. Now how do i code my BFS method and how do i put my starting word as my root node and then it will traverse down the tree while those that are visited it will add into the visited side and then there will be a queue portion so that it knows where to check next time..

    I have google on BFS there are many codes online but i dont know how to apply them to the current code that i have..
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0
    Something similar that i find but i dont understand how the BFS works there...


    dtkachenko.blogspot.sg/2011/12/graphs-and-breadth-wide-search.html
  16. #9
  17. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Sorry, I don't understand what step(s) of the algorithm that you are having problems with.
    It looks like you are looking for an algorithm instead of trying to write java code for an algorithm.
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    9
    Rep Power
    0
    Originally Posted by NormR
    Sorry, I don't understand what step(s) of the algorithm that you are having problems with.
    It looks like you are looking for an algorithm instead of trying to write java code for an algorithm.
    Like what i mention i need to implement BFS into my code... and u can refer to the blog link. its something similar as to what i want.
  20. #11
  21. Contributing User
    Devshed Expert (3500 - 3999 posts)

    Join Date
    Aug 2010
    Location
    Eastern Florida
    Posts
    3,724
    Rep Power
    348
    Sorry, I don't have the algorithm you are looking for.

IMN logo majestic logo threadwatch logo seochat tools logo