Graph theory – Breadth-first search example

I’ve made an example where graph theory and Breadth-first search comes in hand using a simple game. “Wordz” was very popular for a while, if you don’t know the game itself you are probably familiar with the game concept where you have to connect given letters which would then form a word. The more letters in the word, the more points you get. The game in this example has 4×4 letter matrix and the words may be assembled from letters in all directions (not just vertically and horizontally). For 16 given letters that form the 4×4 matrix, all possible words are listed (with matrix coordinates for connecting each letter in the word) using the Breadth-first search algorithm.

You can find the source on my GitHub repo:
https://github.com/lukagabric/WordFinder

There are three main objects: graph node, directional graph and the search controller.

Every node has a list of other nodes it’s adjacent to. Graph adds the nodes via the addAdjacentNode: method.

Using the DirectionalGraph object the nodes are connected forming the Graph.

Search controller is used for performing the Breadth-first search on the DirectionalGraph object.

_nodes array contains all 16 node object representing each letter
_visited is used for the BFS algorithm to track the nodes that have already been visited
_dataSource is the array of words to match BFS results
_allPaths, _allWords and _wordPathDict are used to store BFS results
_startNode and _endNode are the two nodes the BFS is trying to find the path between; the BFS algorithm is executed for each two nodes in the graph

Input

In GraphSearchController.m:

4×4 matrix like the one below is used for graph search example

A B C D
E F G H
I J K L
M N O P

e.g. for a matrix in the image above:

e e y o
d i t j
o u r v
b w u a

inline presentation of the above 4×4 matrix

static NSString *valueString = @”eeyoditjourvbwua”;

Output

All found words and letter locations are logged in the console, e.g.:

‘variety’
(
“v – (3,4)”,
“a – (4,4)”,
“r – (3,3)”,
“i – (2,2)”,
“e – (1,2)”,
“t – (2,3)”,
“y – (1,3)”
)

You can find the source on my GitHub repo:
https://github.com/lukagabric/WordFinder

Related Post

Remember to share...Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedInEmail this to someone

One thought on “Graph theory – Breadth-first search example

Leave a Reply

Your email address will not be published. Required fields are marked *