Fixed-Length excursions in an undirected graph

October 14, 2007 at 2:30 am | Posted in Algorithm, Programming Challenges | Leave a comment

Problem statement

Given two out of n vertices in an undirected graph, is there a path of exactly k distinct vertices (including the endpoints) which connects the two.


The first line of the input will give k.
Each subsequent line will define an edge by listing its endpoints, integers
between 0 and 9 inclusively.


“yes” if vertices 0 and 9 can be connected as described, “no” otherwise.

A depth-first-search solution

It’s obvious that if k > 10, then it’s impossible to navigate from 0 to 9 through k steps. So the answer will be “no”.

If k <= 10, we have to explore the graph by starting from 0, marking each visited node along the path and decreasing the number of steps as we go deeper. If the number of remaining step is equal to 0 and the current node is 9, then the answer is “yes”. Else, we have to go back and explore another path until we find a correct one, or until all paths have been visited.

We will implement the solution of this problem in Java. Here is the class for a node :

public class Node {
int number;
boolean visited;
HashSet children;

public Node(int number) {
this.number = number;
children = new HashSet();



Leave a Comment »

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at
Entries and comments feeds.

%d bloggers like this: