Home arrow Development Cycles arrow Page 4 - 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 - Variations on graph representation
(Page 4 of 7 )

Not all graphs are created equal! The nature of a graph varies widely by the nature of the problem we are trying to solve. Here we give the three most important variations, and how we can handle them.

Directed vs. Undirected Graphs

This is by far the most important variation. In our previous examples we were basically dealing with directed graphs; the word directed here refers to the edges. In all of the examples we have seen, edges had directions. An edge going from A to B is not necessarily also going the other way round. All our examples were based on this.

But, in real life, it doesn’t always work that way. In certain applications, the edges of a graph could have no specific direction. An edge just connects two nodes, and the direction is not important. This is the case with undirected graphs.

An example of a problem with directed graphs is the problem of World Wide Web representations, where pages are represented as nodes, and links are represented as edges. Clearly the direction of a hyperlink matters. If your site links to the Yahoo homepage, it does not mean the same thing as Yahoo putting a link to you on its front page! This is a typical example of a directed graph.

An example of an undirected graph is the initial example we gave about cities, and highways, where cities were represented as nodes, and highways represented as edges. We were interested to find the shortest path from city A to city B. In this example, there are no clear directions for edges. A highway connects two cities, and that’s pretty much it. (Well… I never heard about one way highways anywhere in the world. Please email me if you know any!)

Now, all of our discussion until now was about directed graphs. How can we handle undirected graphs? Should we throw everything out and start over? Absolutely not!

Basically to represent an undirected graph, we use either of the two methods explained above (adjacency lists and adjacency matrices), but for every edge, we actually add two edges in the graph. For example, to add an edge between A and B, we add an edge from A to B, and an edge from B to A.

We have to be careful though, because this approach can cause problems later if we are not careful. It is important to think of both edges as just one edge, not two. Any operation that is done to one must be done to the other.

By the way, directed graphs are drawn without any arrows on the edges. This is to indicate the edges have no specific direction.

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-2017 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials