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

Learning About the Graph Construct using Games, Part III


In the third and final part of our series about the graph construct using games, we learn about Euler tours, and how to use a graph to solve the problem of whether a figure can be drawn without lifting one's pencil from the paper.

Author Info:
By: Mohamed Saad
Rating: 5 stars5 stars5 stars5 stars5 stars / 11
March 22, 2005
TABLE OF CONTENTS:
  1. · Learning About the Graph Construct using Games, Part III
  2. · Conditions for a Solution to Exist
  3. · Representing the Problem as a Graph
  4. · The Steps Required
  5. · Depth First Traversals
  6. · Solving the Problem

print this article
SEARCH DEVARTICLES

Learning About the Graph Construct using Games, Part III - Depth First Traversals
(Page 5 of 6 )

A traversal is like walking on the nodes of a graph. The purpose of a traversal is to visit all nodes of a graph. There are several traversal methods such as Breadth first traversal and Depth first traversal. We will concentrate on depth first traversal here, since it is simpler. Using traversals, we will be able to find paths and loops easily in the graph.

A depth first traversal tries to go as deep as possible in the graph before visiting nodes near to the starting point. For example in a graph like this:

If we start at node a, it will try to go as deep as possible, so a possible scenario could be… a->b->c->d->e->f->g->h (a depth first traversal is clearly not unique, we could have started with the path to c)

Depth first traversal is extremely easy to code. For every node, we mark it as visited and recursively call the traversal for each of the unvisited neighboring nodes. (I hope you are familiar with the concept of recursion. If not, please check my article here: http://www.devshed.com/c/a/Practices/Solving-Problems-with-Recursion/)

Here is the code for a simple depth first traversal:

void depthFirstTraversal(int u)
{
  System.out.println("Visiting node "+u);
  visited[u]=true;
  for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
  {
    if(!visited[w.id])
      depthFirstTraversal(w.id,v,color);
  }
}

We are assuming the same adjacency list representation from parts 1 and 2. I hope you haven't already forgotten about them. Each node has a linked list holding all the nodes to which it is connected.

So, what does Depth First traversal have to do with path finding? A lot, actually! A slight modification of this function will allow us to find a path (or a loop) between two nodes in a graph.

The idea is simple. To find a path from u to v, we will keep traversing the graph starting at u till we hit the node v. Before we visit any node, we mark the edge leading to it as taken. If no path is found through this path, we reset the state of the edge to not taken. When we stop after hitting v, the path leading from u to v will be marked as taken. Pretty simple, eh?

Here is the modified function:

boolean markPath(int u,int v,int color)
{
  visited[u]=true;
  for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
  {
    if(w.color!=0)
      continue;
    markColor(u,w.id,color);
    if(w.id==v)
      return true;
    if(!visited[w.id])
      if(markPath(w.id,v,color))
        return true;
      markColor(u,w.id,0);
  }
  return false;
}

You may notice we have an extra parameter, called color. This is because, as we mentioned before, we are going to be finding a path, and several loops, so it is important to distinguish them. We mark the edge we take by a certain color, to indicate it belongs to a certain loop, or path.

The second observation is the markColor function. What is it? Remember in part 1 when we talked about undirected graphs, and how they are represented by two edges between any two nodes instead of one. The two edges must be treated as one. The markColor function simply colors the two versions of the edge: the one going from u to v, and the one going from v to u.

void markColor(int u,int v,int color)
{//mark the 2 versions of the edge (u,v) with color
  for(node2 w=((node)(data.elementAt(u))).links;w!=null;w=w.next)
  {
    if(w.id==v)
    {
      w.color=color;
      break;
    }
  }
  for(node2 w=((node)(data.elementAt(v))).links;w!=null;w=w.next)
  {
    if(w.id==u)
    {
      w.color=color;
      break;
    }
  }
}


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