Home arrow Development Cycles arrow Page 5 - 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 - Weighted Edges
(Page 5 of 7 )

This is easier than the previous case. In our previous examples, we were only interested in the existence of an edge. In some applications, edges also have weights on them. For example, in the cities and highways example, we could put the length of a highway as a weight for the edge between two cities. This will allow us to find the shortest path between two cities precisely.

How could we add weighted edges to the graphs we just created? This one is easy. For an adjacency matrix, we just write the weight of the edge in the corresponding entry in the matrix rather than just “1” and “0”. Notice that in some applications, “0” is a valid weight. In this case, it can’t be used as a “no-edge” value. We will have to look for another value in this case. For example, this graph: 
 


Fig 4.
Graphs with weighted edges…

Would be represented by this array: 
 


Fig 4b.
… can still be represented using adjacency matrix

We have used an symbol in place of non-existent edges. In reality, we can use any invalid value to denote that no edge exists here.

In the case of an adjacency list, we can add a new field in every node of every linked list, which holds the weight of that edge.

For example, the same graph above would be represented like this:

 

Fig 4c. … Adjacency list representation of weighted graphs

The first node in the first linked list, means that node a is connected to node f with a weight of 12. (Notice that node counting starts at 0 for obvious reasons!)


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