Learning About the Graph Construct using Games, Part 1
(Page 1 of 7 )
Certain everyday problems are easier to solve using the graph construct than any other way, such as the classic "shortest distance between cities" problem. Others are ones you might not expect. In this article, we will play some games to help us understand how we can use the graph construct.
Can you draw this shape using a pencil without passing over any line twice, and without removing the pencil from paper? Can you evenly divide 8 liters of water by using 3 jugs of volumes 3, 5 and 8 liters? Believe me, after reading this article, you will never get stuck with any of these problems again. We are going to solve both problems and much more. Today we are going to explore the magic world of graphs.
Before we start
Before we turn our attention to solving the puzzles just mentioned, we need to quickly introduce the graph data structure. Let’s start with this immediately.
What are graphs?
Graphs are one of the advanced data structures. A graph consists of some nodes connected together with edges. A typical graph would look like this…
Fig 1. A typical graph
Now, even before we say anything more, several questions arise. Most important of all, why would we need to use graphs? What is the motivation behind using such a complex data structure?
There are lots of good reasons. Graphs seem to be the perfect data structure to represent several kinds of problems. For example, if you are trying to solve the problem of finding the nearest two cities on a map, graphs can be very helpful. You can represent cities as nodes, and represent highways between cities as edges. This gives us a graph. We will later see how we can find the shortest path in a graph.
Graphs shine in other situations too. Graphs are used in games to find the best paths in maps. This is used in genres such as RTS games and First Person Shooters.
Search Engines (e.g. Google), also employ graphs in their work. The structure of the Web is represented as a graph. Web pages are represented as nodes, and hyperlinks are represented as edges. So, if Web page A contains a link to Web page B, then an edge exists between their corresponding nodes in the graph. By the way, knowing that Google indexes more than four billion pages, that must be a seriously enormous graph -- containing more than four billion nodes, and certainly many more edges!
As you can see, graphs are very good at representing certain kinds of complex problems. Now that we appreciate the value of graphs, it is time to move to the next step. We have to ask ourselves the fundamental question in data structures: how can we represent graphs in the memory of a computer?
As you know, the memory of a computer can be thought of as a gigantic one-dimensional array. How can we fit a graph into this? Where will the nodes go? Where will the edges go? These are all very good questions. In fact, there are several representations for a graph, depending on the nature and certain properties of the graph.
Next: Representing a Graph >>
More Development Cycles Articles
More By Mohamed Saad
