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.

Input

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.

Output

“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();
}
}

sd

Advertisements

Create a free website or blog at WordPress.com.
Entries and comments feeds.