A very similar problem to the Traveling Salesperson problem is finding the best route. And this one you most likely have directly encountered. Have you ever tried to find a way to a destination using more than one map finding software? Maybe you used Google Maps, MapQuest, and your car’s GPS, and they all gave…
Let’s look at one of the oldest examples of a graph problem. The idea comes from a real life problem where a salesperson needs to visit a series of cities to visit potential clients. A company wanted to find the most efficient path for him to take to visit all of the cities he needed…
Graph problems look similar to tree problems, but there are a few differences. Trees have a series of nodes. Each node may have zero, one, or multiple child nodes, but it can only be referenced from parent to child, or child to parent. In a graph, each node is called a vertex. Each Vertex can…
In some cases you will know the path, or partial path, to the node you are looking for. This is often found when you are searching a HTML file (the Document Object Model or DOM), XML file, or similar storage structure. In that case, you can use something similar to XPATH for XML documents, or…
A depth first search algorithm analyzes the first child node for a match, and if one is not found, then it moves to that nodes children. This repeats until either a depth limit is reached, or there are no more children. Because of the complexity of some trees, consider a list of all websites to…
The first, and one of the most common methods to search is using a breadth first search (BFS) pattern. In this case, you start at the root node of the tree, and evaluate the first child determining if you have a match. If not, you move to its sibling and then the next, until there…
Data transformation is often simple like splitting a full name into the first and last, or vice versa. However, sometimes it is more complicated, much more complicated. I once wrote a data converter which had to convert data stored in a file with the size of data store being a certain number of bytes into…
An insertion sort is a bit of a special case. It assumes that you will be given a set of values over time, and as you get them, you will insert the value into its correct location based upon the given values. Depending upon the data, and size, you could utilize different types of sort,…
