# Breadth First vs. Depth First Search

**URL:** <https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853>\
**Category:** open source\
**Created:** [April 25, 2006, 12:52am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853 "2006-04-25T00:52:52Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 12:52am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/1 "2006-04-25T00:52:52Z")

</div>

So, in preperation for the computer contest (which you may remember I qualified for a while back), I did a 9 poit (the highest amount) problem. Turns out… it was **really** difficult. **Edit** : By the way, for anybody who can’t tell… this is in _ **Java** _. You will also need JDK 1.5 (uses scanner).

My teacher had no idea how to do it, and as we were leaving, he thought of the phrase “breadth vs. depth search,” but I don’t think he knew exactly how to program it.

So, I showed the problem to my dad, and he immediately knew about the search algorithm, but wasn’t so good at programming it.

It’s taken us about three hours, but I present to you… our finished project!

```auto
import java.util.*;
import java.io.*;

public class pr93 {
	public static void main (String args[]) throws IOException {
		Scanner scanner = new Scanner (new FileReader ("pr93.txt"));
		
		int dictionaryLength = scanner.nextInt();
		ArrayList<String> words = new ArrayList<String>();
		int testCases = scanner.nextInt();
		
		
		scanner.nextLine();
		
		for (int i=0; i<dictionaryLength; i++) {
			words.add(scanner.nextLine());
		}
		
		for (int i=0; i<testCases; i++) {
			ArrayList<Path> potentialPaths = new ArrayList<Path>();
			ArrayList<Path> newPaths = new ArrayList<Path>();
			
			boolean printed = false;
			
			String start = scanner.next();
			String goal = scanner.next();
			
			for (int j=0; j<words.size(); j++) {
				if (pr93.areLinked(words.get(j), start)) {
					Path path = new Path (start, words.get(j));
					potentialPaths.add(path);
				}
			}
			
			for (int j=0; j<words.size()&&printed==false; j++) {					
				for (int m=0; m<potentialPaths.size(); m++) {
					if (potentialPaths.get(m).isFinished(goal)) {
						potentialPaths.get(m).printPath();
						printed = true;
						break;
					}
				}
				
				potentialPaths = pr93.buildNewPaths(words, potentialPaths, newPaths);
			}
			
			System.out.println();
		}
	}
	
	public static boolean areLinked (String word1, String word2) {
		int different = 0;
		StringBuffer wordOne = new StringBuffer(word1);
		StringBuffer wordTwo = new StringBuffer(word2);
		
		for (int i=0; i<word1.length(); i++) {
			if (wordOne.charAt(i)!=wordTwo.charAt(i)) {
				different++;
				
				if (different>1) return false;
			}
		}
		
		if (different==0) {
			return false;
		}
		
		return true;
	}
	
	public static ArrayList<Path> buildNewPaths (ArrayList<String> words, ArrayList<Path> oldPaths, ArrayList<Path> newPaths) {
		for (int j=0; j<oldPaths.size(); j++) {
			String lastWord = oldPaths.get(j).lastWord();			
			for (int m=0; m<words.size(); m++) {
				
				if (pr93.areLinked(lastWord, words.get(m)) &&
					!oldPaths.get(j).hasWord(words.get(m))) {
						Path newPath = new Path(oldPaths.get(j), words.get(m));
						newPaths.add(newPath);
				}
			}
		}
		
		return newPaths;
	}
}

class Path {
	ArrayList<String> path = new ArrayList<String>();
	
	public Path (String start, String end) {
		path.add(start);
		path.add(end);
	}
	
	public Path (Path oldPath, String word) {
		path = new ArrayList<String>(oldPath.getPath());
		path.add(word);
	}
	
	public void add (String word) {
		path.add(word);
	}
	
	public ArrayList<String> getPath () {
		return path;
	}
	
	public void printPath () {		
		for (int i=0; i<path.size(); i++) {
			System.out.println(path.get(i));
		}
	}
	
	public String toString () {
		return path.toString();
	}
	
	public String lastWord () {
		return path.get(path.size()-1);
	}
	
	public boolean isFinished (String goal) {
		if (path.get(path.size()-1).equals(goal)) {
			return true;
		}
		
		return false;
	}
	
	public boolean hasWord (String word) {
		return path.contains(word);
	}
}

```

**[size=4]USAGE[/size]**

It’s actually really simple. Given a dictionary, it will find the shortest path between two words. The sample input looks like this:

```auto
8 3
that
this
what
then
when
than
thin
thus
this that
what when
when then

```

The 8 represents the number of words in the dictionary (always all the same length), and the three represents how many chains you will need to find.

The sample output looks like this:

```auto
this
thin
than
that

what
that
than
then
when

when
then

```

Huzzah!

[whisper]I also could have taken the brute-force approach, but ■■■■ that wouldn’t have been nearly as pretty![/whisper]

---

<div class="post-metadata">

**Author:** ![MTsoul](https://avatars.discourse-cdn.com/v4/letter/m/91b2a8/32.png) [@MTsoul](https://forum.kirupa.com/u/MTsoul)\
**Post date:** [April 25, 2006, 12:59am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/2 "2006-04-25T00:59:59Z")

</div>

I don’t get it ☹

---

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 1:00am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/3 "2006-04-25T01:00:56Z")

</div>

It’ll find a chain of words with only one letter different…

---

<div class="post-metadata">

**Author:** ![MTsoul](https://avatars.discourse-cdn.com/v4/letter/m/91b2a8/32.png) [@MTsoul](https://forum.kirupa.com/u/MTsoul)\
**Post date:** [April 25, 2006, 1:05am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/4 "2006-04-25T01:05:40Z")

</div>

Hmm that is pretty interesting. I’ve never seen anything like it before.

---

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 1:34am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/5 "2006-04-25T01:34:07Z")

</div>

Yeah, I’m proud. It was hard. 😃

---

<div class="post-metadata">

**Author:** ![cr125rider](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/cr125rider/32/534_2.png) [@cr125rider](https://forum.kirupa.com/u/cr125rider)\
**Post date:** [April 25, 2006, 1:59am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/6 "2006-04-25T01:59:15Z")

</div>

That is super cool dude!

---

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 2:08am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/7 "2006-04-25T02:08:28Z")

</div>

Hehe. Thanks 😃

---

<div class="post-metadata">

**Author:** ![codemonkeypete](https://avatars.discourse-cdn.com/v4/letter/c/b77776/32.png) [@codemonkeypete](https://forum.kirupa.com/u/codemonkeypete)\
**Post date:** [April 25, 2006, 2:14am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/8 "2006-04-25T02:14:28Z")

</div>

thats bloody cool nokrev - we used to do this as kids on rainy days…(sad childhood i had!!!) … very good example of java. mind converting it to AScript for me? :smirk2:

---

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 2:15am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/9 "2006-04-25T02:15:23Z")

</div>

Err… I don’t know AS… I don’t use Flash.

---

<div class="post-metadata">

**Author:** ![glosrfc](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/glosrfc/32/8334_2.png) [@glosrfc](https://forum.kirupa.com/u/glosrfc)\
**Post date:** [April 25, 2006, 4:22am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/10 "2006-04-25T04:22:43Z")

</div>

I suppose this could be developed further to solve word-chain puzzles, _i.e._ where you transform one word into another word, _e.g._ slow to fast, warm to cold, hard to easy.  
_Viz._ cat --\> can --\> con --\> cog --\> dog.

_n.b._ only one letter can altered at a time and the order of the letters can’t be changed.

[SIZE=“1”]Sorry, I couldn’t resist practising the use of so many abbreviations[/SIZE] 😃

* * *

[Mazda Mxr-01](http://www.ford-wiki.com/wiki/Mazda_MXR-01)

---

<div class="post-metadata">

**Author:** ![codemonkeypete](https://avatars.discourse-cdn.com/v4/letter/c/b77776/32.png) [@codemonkeypete](https://forum.kirupa.com/u/codemonkeypete)\
**Post date:** [April 25, 2006, 5:20am UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/11 "2006-04-25T05:20:39Z")

</div>

which is exacley what this thing does… is it not?

---

<div class="post-metadata">

**Author:** ![Jeff\_Wheeler](https://avatars.discourse-cdn.com/v4/letter/j/59ef9b/32.png) [@Jeff\_Wheeler](https://forum.kirupa.com/u/Jeff_Wheeler)\
**Post date:** [April 25, 2006, 1:25pm UTC](https://forum.kirupa.com/t/breadth-first-vs-depth-first-search/186853/12 "2006-04-25T13:25:17Z")

</div>

Yeah, that’s exactly what it does. 😉