Home arrow Development Cycles arrow Page 3 - Learning About the Graph Construct using Games, Part 1
DEVELOPMENT CYCLES

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
TABLE OF CONTENTS:
  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
SEARCH DEVARTICLES

Learning About the Graph Construct using Games, Part 1 - Adjacency List Representation
(Page 3 of 7 )

The adjacency list method is a different representation that is quite good when graphs are not dense enough. How does it work? This is simple. All it does is store a series of linked lists, one linked list per node. Each linked list stores the edges coming out of a certain node.

In other words, the first linked list stores the ids of all nodes node 1 is connected to. The second linked list stores the ids of all nodes node 2 is connected to, and so on. Fir example, if we look at the following graph: 
 


Fig 3.
This graph…

It would be represented that way:

 

Fig 3b.
… is represented by this adjacency list.


Notice that the number of linked lists is equal to the number of nodes. The first linked list is empty, since node one is not connected to anything. The second linked list has two elements, since node two is connected to both node one and node three. We are basically using an array of linked lists. I hope this expression doesn’t scare you. It is simpler than it sounds.

What are the advantages of this representations?

  1. If the graph is not very dense, this representation is great, because it doesn’t waste memory locations for non-existent edges.
  2. It is easy to list all of the edges coming out of a node. The time taken is exactly equal to the number of edges, unlike what happens when using adjacency matrices.

What are the disadvantages?

  1. If the graph is very dense, (for example, we have a fully connected graph), the memory taken is more than that taken by adjacency matrices, because of the extra allocation for the pointers in the linked list.
  2. To answer the question “Does an edge exist between nodes A and B?”, you must visit all nodes of the linked list of A (as opposed to looking up one entry when using adjacency matrix).

The bottom line is, adjacency lists shine when graphs are not very dense. On the other hand, an adjacency matrix is great when graphs are very dense.

This is going to be the last bit of theory, before we jump straight into the first game.

Before we drift away from the topic of representation, I want to quickly touch on a very important point. It is about important variations.


blog comments powered by Disqus
DEVELOPMENT CYCLES ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




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