Home arrow Development Cycles arrow Learning About the Graph Construct using Games, Part 1

Learning About the Graph Construct using Games, Part 1

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.

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 24
February 23, 2005
  1. · Learning About the Graph Construct using Games, Part 1
  2. · Representing a Graph
  3. · Adjacency List Representation
  4. · Variations on graph representation
  5. · Weighted Edges
  6. · Labelled nodes
  7. · Building the Graph

print this article

Learning About the Graph Construct using Games, Part 1
(Page 1 of 7 )

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.

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials