Created
November 22, 2017 06:45
-
-
Save Ethan826/8d1939cc5bafd57e14a2c90661db11b0 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
public class bfs { | |
public static void main(String[] args) { | |
// A hashmap is also called an "associative array." Think of it as an | |
// array, but instead of being indexed with numbers 0 to n-1, it is | |
// indexed based on the keys you supply. In this case, the hashmap has | |
// keys that are strings, and values that are arrays of strings. | |
HashMap<String, String[]> family = new HashMap<String, String[]>(); | |
// Java doesn't give us hashmap literals, so we have to build them up by | |
// inserting key-value pairs one by one. | |
family.put("belle", new String[] {"ethan", "madigan"}); | |
family.put("betty", new String[] {}); | |
family.put("ethan", new String[] {"steve", "judy"}); | |
family.put("jonathan", new String[] {"marshall", "betty"}); | |
family.put("judy", new String[] {}); | |
family.put("madigan", new String[] {"jonathan", "maggie"}); | |
family.put("maggie", new String[] {}); | |
family.put("marshall", new String[] {}); | |
family.put("milo", new String[] {"ethan", "madigan"}); | |
family.put("steve", new String[] {}); | |
// Method call to actually perform the breadth-first search. | |
printResult(bfs(family, "belle", "marshall")); | |
printResult(bfs(family, "milo", "steve")); | |
printResult(bfs(family, "maggie", "steve")); | |
} | |
// The walk-through assumes the "belle" to "marshall" path | |
public static LinkedList<String> bfs(HashMap<String, String[]> family, String beginNode, String endNode) { | |
// A `LinkedList` is a last-in, first-out stack (like a stack of plates | |
// in a cafeteria). | |
// Set `initalPath` to ["belle"] | |
LinkedList<String> initialPath = new LinkedList<String>(); | |
initialPath.push(beginNode); | |
// Set `paths` to [["belle"]] | |
LinkedList<LinkedList<String>> paths = new LinkedList<LinkedList<String>>(); | |
paths.push(initialPath); | |
// Loop until `paths` is empty. The first time through, `paths` = [["belle"]] | |
while(paths.size() > 0) { | |
// The `pop()` method takes removes and returns the item at the top of the stack. | |
// Now `path` = ["belle"] and `paths` = [] | |
LinkedList<String> path = paths.pop(); | |
// The `peek()` method copies the top of a stack without popping it. | |
// `node` now equals "belle" | |
String node = path.peek(); | |
// The first time through, `node` is "belle", `endNode` is | |
// "marshall", so this evaluates to `false`. | |
if(node == endNode) { | |
return path; | |
} | |
// This is where we build `paths` back up. `nextNode` is going to be | |
// bound to each parent of "belle": "ethan", then "madigan" (the | |
// `get()` method retrieves the value from the hashmap by key). So | |
// by the time this `for` loop completes `paths` will equal | |
// | |
// [["belle", "ethan"], ["belle", "madigan"]]. | |
// | |
// When the `while` loop above comes around again, the `for` loop | |
// below will add the next generation: | |
// | |
// ["belle", "madigan", "maggie"], ["belle", "madigan", "jonathan"]] | |
// | |
// The final time through the `while` loop we'll get | |
// | |
// [["belle", "madigan", "jonathan", "marshall"]], | |
// | |
// The fact that we look up parents before adding to the stack means | |
// we immediately prune branches that have dead-ended. | |
// | |
// You can see why it's called a breadth-first search: it branches | |
// fully at each generation until short-circuiting after it | |
// encounters the `endNode` | |
for(String nextNode : family.get(node)) { | |
// We have to copy `path` or else we would mutate the *original* | |
// version of `path` defined above when we `push`ed on `nextNode`. | |
// `pathCopy` now equals [["belle"]] | |
LinkedList<String> pathCopy = new LinkedList<String>(path); | |
// `pathCopy` will equal `[["belle", "ethan"]]` in one iteration | |
// of the `for` loop and will equal [["belle", "madigan"]] in | |
// the following iteration | |
pathCopy.push(nextNode); | |
// Uncomment me to see what happens on each iteration | |
// printResult(pathCopy); | |
// `paths` becomes [["belle", "ethan"]] the first time this | |
// `for` loop iterates, and | |
// [["belle", "ethan"], ["belle", "madigan"]] | |
// the second time | |
paths.push(pathCopy); | |
} | |
} | |
return new LinkedList<String>(); | |
} | |
// Helper method to print the results | |
public static void printResult(LinkedList<String> result) { | |
LinkedList<String> resultCopy = new LinkedList<String>(result); | |
// We used a stack in the `bfs` method, which actually causes the | |
// result to be backwards. So let's reverse the result. | |
Collections.reverse(resultCopy); | |
// We have to fiddle with types to get `println` to act the right way | |
// (only the array class has a `toString`) method, but to use it, we | |
// have to turn our `LinkedList` into an array. | |
System.out.println(Arrays.toString(resultCopy.toArray())); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment