Algorithms For Dummies

  Reconnecting the Dots 

     173

IN THIS CHAPTER

 

» Working with graphs

 

» Performing sorting tasks

 

» Reducing the tree size

 

» Locating the shortest route between 

two points

Reconnecting the Dots

T

his chapter is about working with graphs. You use graphs every day to per-

form a range of tasks. A graph is simply a set of vertexes, nodes, or points 

connected by edges, arcs, or lines. Putting this definition in simpler terms, 

every time you use a map, you use a graph. The starting point, intermediate 

points, and destination are all nodes. These nodes connect to each other with 

streets, which represent the lines. Using graphs enables you to describe relation-

ships of various sorts. The reason that Global Positioning System (GPS) setups 

work is that you can use math to describe the relationships between points on the 

map and the streets that connect them. In fact, by the time you finish this chapter, 

you understand the basis used to create a GPS (but not necessarily the mechanics 

of making it happen). Of course, the fundamental requirement for using a graph 

to create a GPS is the capability to search for connections between points on the 

map, as discussed in the first section of the chapter.

To make sense of a graph, you need to sort the nodes, as described in the second 

section  of  the  chapter,  to  create  a  specific  organization.  Without  organization, 

making any sort of decision becomes impossible. An algorithm might end up 

going in circles or giving inconvenient output. For example, some early GPS set-

ups didn’t correctly find the shortest distance between two points, or sometimes 

ended up sending someone to the wrong place. Part of the reason for these prob-

lems is the need to sort the data so that you can view it in the same manner each 

time the algorithm traverses the nodes (providing you with a route between your 

home and your business).

When you view a map, you don’t look at the information in the lower-right corner 

when you actually need to work with locations and roads in the upper-left corner. 

Chapter