Home arrow Development Cycles arrow Page 2 - 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 - Representing a Graph
(Page 2 of 7 )

We are going to explain here the two most famous and most widely used representations: the adjacency matrix method, and the adjacency list method.

Adjacency Matrix Representation

The first representation we are going to discuss is quite straightforward. The graph could be represented by just one two-dimensional array. How? We use a two-dimensional array whose dimensions are n*n, where n is the number of nodes in the graph. Each entry in the array says whether there is an edge between those two nodes or not.

For example, look at the following simple graph:


Fig 2.
This small graph…

It would be represented by the following array: 

Fig 2b.
… is represented by this matrix

Notice that the array dimensions are 4*4, which is the number of nodes in the graph.

Notice also that the second row “1 0 1 0” indicates that node two  is connected to nodes one and three, but not connected to node four or to itself. The other rows can be interpreted easily the same way. Notice that first row is all zeroes, since node one doesn’t point to any other nodes. I hope you are starting to get the idea.

What are the advantages of this representation? It is a pretty attractive representation, with have the following advantages:

  1. It is a simple and really easy to comprehend representation.
  2. It is really easy to answer the question, “does a link exist between nodes A and B” (you need to just look up the entry of row A, column B).
  3. Some questions such as “Which nodes link to a certain node A?” are easier to answer than with other representations.

Now, what is wrong with this representation? Sadly, there are two main bad points about this representation.

  1. If the graph doesn’t have a lot of edges, the array representation wastes a lot of memory. For example, for a 100 node graph with 150 edges, we will end up with an array taking up 10,000 numbers, with only 150 of them being used.
  2. If you are asked “Which edges are coming out of a certain node A?”, you have to go over the entire A row to answer this question. In other words, in a 1,000 node graph, if node A is only connected to node B, you still must check all 1000 entries in the row of node A to discover this. This can be a serious waste of time.

To put it in another way, the array representation has serious problems when graphs are not very dense. On the other hand, if the graph is dense enough, this representation is very strong, and should definitely be used.

What if the graph is not dense enough? For this case, we have the adjacency list representation.

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