Graph & Tree algorithms

Graphs and Trees are at the heart of a computer and very useful in representing and resolving many real world problems like calculating the best paths between cities (Garmin, TomTom) and other famous ones like Facebook search and Google search engine crawling. If you know any programming language, you might have heard of garbage collection and for that the typical graph search called Breadth First Search is used. In this post, I will try to cover the following topics.

• Graphs – directed, undirected and special case of directed which are called Directed Acyclic Graph(DAG)
• Trees – Binary trees and also most useful version of it, the Binary Search Trees (BST)
• Standard traversal techniques – Breadth First Search (BFS), Depth First Search (DFS).

I know it will be a bit lengthy but I assure you it will be worth going through. I will try to cover the following topics in another post.

• Overview of shortest path algorithms – BFS, Dijkstra and Bellman Ford
• BST Search, Pre-order, In-order and Post-order.

Graphs

A graph consists of vertices (nodes) and edges. Think vertex as a point or place and the edge is the line/path connecting two vertices. In a typical graph and tree nodes there will be some kind of information is stored and the vertices will be associated with some cost. There are mainly two types of graphs and they are undirected and directed graphs.

In undirected graphs, all of the edges are undirected which means we can travel in either direction. So if we have an edge between vertex A and B, then we can travel from A to B and also from B to A. Following is the sample undirected graph.

A Undirected Graph

Here in this undirected graph,

• The vertices are – A, B, C, D, E and F.
• The edges are – {A, B}, {A, C}, {B, C}, {B, D}, {C, D}, {D, E}, {D, F} and {E, F}. Here edge {A, B} means, we can move from A to B and also from B to A.

In directed graphs, all of the edges are directed which means we can only travel in the direction of an edge. So for example, if we have an edge between vertices A and B, then we can only go from A to B and not from B to A. If we need to go from B to A, then there should be another edge which should point B to A. Following is the sample directed graph.

Directed Graph

Here in this directed graph,

• The vertices are – A, B, C, D, E and F.
• The edges are – (A, C), (B, A), (B, D), (C, D), (D, E), (D, F) and (F, E). Here edge (A, C) means, we can only move from A to C and not from C to A.

The graphs can be mixed with both directed and undirected edges but let us keep this aspect away in this post to understand the core concepts better. Just an FYI the undirected edges are represented by curly braces ‘{}’ where as directed edges are represented by ‘()’.

Directed Acyclic Graphs – DAG

This is a variation of standard directed graph without any cycle paths. It means there is no path where we can start from a vertex and comeback to the same starting vertex by following any path. By the way, cycles in the graph are very important and we need to be very careful about it. Otherwise, we could end up writing infinite algorithms which will never be completed.

The above diagram does not have a cycle, so it is a DAG. Basically we can start from any node and won’t come back to the same starting node.

If we carefully look at the above listed directed graph, there is a cycle path and because of that, this graph is not a DAG. We can start from node A and come back to it by following the path.

Trees

This is another variation or we may call it subset of a graph. So we can say, all trees are graphs but not all graphs are trees. It is almost similar to the real world tree. It will have one top level vertex which is called root, and every node will have either zero or more child vertices. The best examples of tree data structure are family relationship and a company organization chart. Few important things to note down here,

• There will not be any cycles in this.
• Every node will have only one parent except the root which will not have any.

Following is a sample tree structure.

A Tree

As a standard the tree is represented from top to bottom. In this, the top node A is called as root of this tree as there are no parents to it. Then all of the child vertices (B, C and D) of A are represented on next level. All of the nodes which don’t have any child nodes (E, F, G, H and D) are called leaf nodes.

DAG vs Tree

As you can see by now both the DAG and tree will not have any cycle paths but there is a key difference that is, in DAG there can be nodes with multiple parents but where as in tree, every node will have either a single parent or none. Following diagrams depicts this difference.

DAG vs Tree

In the above DAG example, D has two parents B and C and this is not possible in the tree. In tree example above, D has just one parent C.

Binary Tree

This is a version of the tree structure and in this every node can have strictly at most two child nodes. That means a node either can have two child nodes, just one or simply no child nodes in which case we call them leaf nodes. Following is a sample binary tree.

Binary Tree

Binary Search Tree (BST)

This is a most useful version of the Binary Tree in which every node (including root) holds the following two properties.

• The left child node (if exists) should contain the value which is less than or equal to the parent.
• The right child node (if exists) should contain the value which is greater than or equal to the parent.

The above ordering property is really useful which we can understand clearly when we go through some of the search algorithms (especially the Binary search).

For simplicity, we will use the numbers in the nodes to show this relationship but the nodes can contain any information as long they are comparable. That means we should be able to compare them in some way and tell, whether those are equal or whether which one is greater.  Following is a sample BST,

Binary Search Tree

Data Structure representation

Hopefully all of the above details provide the insights on graphs and tree data structures. Before we get on to the actual traversals and searching algorithms, it is essential and useful to understand how they are represented or stored them in programming languages.

Following are the two mostly used representations.

Adjacency Lists

In this, the node is represented by an object and the edge is represented by the object references. Every object will have some data and a list of adjacent node references or a method which can return the list of adjacent nodes. If there are no neighbors, then it will be null or empty. So in nutshell, we have some mechanism to quickly find out neighbors for a given node.

There is also another way to represent using adjacency lists which having a map which contains the key as the node and the value is list containing all of its neighbors. In this case, we can simply get all of its neighbors of a node N by simply looking for a key N in the map. That is we could say the neighbors of node N are simply Adj[N] where Adj is the adjacency map. Following is a sample representation of this representation.

Graph Adjacency list representation

Matrix representation

In this, we will use a double dimensional array where rows and columns represent the nodes and will use some kind of special value or actual edge cost as the value if they are connected. Following is sample example of representation.

Graph matrix representation

In the above, we have used 1 to represent the edge and 0 for no edge and we are looking from row to column. That is Array[B][C] is 1 as there is edge from B to C but Array[C][B] is zero as there is no edge between C to B. We could also use some value to represent the actual cost and use some sentinel (infinity or -1) value to represent no connection between the nodes. Yes, it is not a regulatory object oriented design but it have its own advantages like accessing random node and get the edge cost of a neighbor in constant time.

Searching Algorithms

There are two main search techniques which work fine on both the graphs and all versions of trees. It is just that we need to be careful about the cycles in graphs.

Breadth First Search (BFS)

In this, we will search or examine all of the sibling nodes first before going to its child nodes. In other words, we start from the source node (root node in trees) and visit all of the nodes reachable (neighboring nodes) from the source. Then we take each neighbor node and perform the same operation recursively until we reach destination node or till we run out of graph. The following color coded diagrams depicts this searching.

Breadth First Search

In this, the starting node is S and the target node is V.  In this,

• Visit all of the nodes reachable from S. So we visit nodes A & C. These are the nodes reachable in 1 move or nodes at level 1.
• Then visit the nodes reachable from A & C. So we visit nodes B, D & E. These are the nodes reachable in 2 moves or we can say nodes at level 2.
• Then visit the nodes reachable from B, D & E. So we visit nodes F & V. These are the nodes reachable in 3 moves or we can say at level 3.

Advantages of this approach are,

• The path from which we first time reach a node can be considered as shortest path if there are no weights/costs to the edges or they might be constant. This is called single source shortest paths.
• This can be used in finding friends in social network sites like Facebook, Google+ and also linked in. In linked in, you might have seen the 1^st, 2^nd or 3^rd degree as super scripts to the friend’s names – it means that they are reachable in 1 move, 2 moves and 3 moves from you and now you might guess how they calculate that J

BFS implementation

We can implement this in multiple ways. One of the most popular ways is by using Queue data structure and other by using lists to maintain the front and next tier nodes. Following is the java implementation of this algorithm.

  public static void graphBFSByQueue(Node<String> source) {
    //if empty graph, then return.
    if (null == source) {
      return;
    }
    Queue<Node<String>> queue = new LinkedList<Node<String>>();
    //add source to queue.
    queue.add(source);
    visitNode(source);
    source.visited = true;
    while (!queue.isEmpty()) {
      Node<String> currentNode = queue.poll();
      //check if we reached out target node
      if (currentNode.equals(targetNode)) {
        return; // we have found our target node V.
      }
      //Add all of unvisited neighbors to the queue. We add only unvisited nodes to avoid cycles.
      for (Node<String> neighbor : currentNode.neighbors) {
        if (!neighbor.visited) {
          visitNode(neighbor);
          neighbor.visited = true; //mark it as visited
          queue.add(neighbor);
        }
      }
    }
  }

  public static void graphBFSByLevelList(Node<String> source) {
    //if empty graph, then return.
    if (null == source) {
      return;
    }
    Set<Node<String>> frontier = new HashSet<Node<String>>();
    //this will be useful to identify what we visited so far and also its level
    //if we dont need level, we could just use a Set or List
    HashMap<Node<String>, Integer> level = new HashMap<Node<String>, Integer>();
    int moves = 0;
    //add source to frontier.
    frontier.add(source);
    visitNode(source);
    level.put(source, moves);
    while (!frontier.isEmpty()) {
      Set<Node<String>> next = new HashSet<Node<String>>();
      for (Node<String> parent : frontier) {
        for (Node<String> neighbor : parent.neighbors) {
          if (!level.containsKey(neighbor)) {
            visitNode(neighbor);
            level.put(neighbor, moves);
            next.add(neighbor);
          }
          //check if we reached out target node
          if (neighbor.equals(targetNode)) {
            return; // we have found our target node V.
          }
        }//inner for
      }//outer for
      moves++;
      frontier = next;
    }//while
  }

  public static void treeBFSByQueue(Node<String> root) {
    //if empty graph, then return.
    if (null == root) {
      return;
    }
    Queue<Node<String>> queue = new LinkedList<Node<String>>();
    //add root to queue.
    queue.add(root);
    while (!queue.isEmpty()) {
      Node<String> currentNode = queue.poll();
      visitNode(currentNode);
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //Add all of unvisited neighbors to the queue. We add only unvisited nodes to avoid cycles.
      for (Node<String> neighbor : currentNode.neighbors) {
        queue.add(neighbor);
      }
    }
  }

  public static void treeBFSByLevelList(Node<String> root) {
    //if empty graph, then return.
    if (null == root) {
      return;
    }
    List<Node<String>> frontier = new ArrayList<Node<String>>();
    //add root to frontier.
    frontier.add(root);
    while (!frontier.isEmpty()) {
      List<Node<String>> next = new ArrayList<Node<String>>();
      for (Node<String> parent : frontier) {
        visitNode(parent);
        //check if we reached out target node
        if (parent.equals(targetTreeNode)) {
          return; // we have found our target node V.
        }

        for (Node<String> neighbor : parent.neighbors) {
          next.add(neighbor);
        }//inner for
      }//outer for
      frontier = next;
    }//while
  }

Depth First Search (DFS)
In this, we will search a node and all of its child nodes before proceeding to its siblings. This is similar to the maze searching. We search a full depth of the path and if we don’t find target path, we backtrack one level at time and search all other available sub paths.
Depth First Search
In this,

Start at node S.

Visit A
Visit B
Backtrack to A as B don’t have any child nodes
Backtrack to S as A don’t have any unvisited child nodes
Backtrack to node S

Visit C
Visit D
Visit E
Visit F
Visit V – reached searching node so exit.





The path to node V from S is “S – C – D – E – F – V” and the length of it is 5. In the same graph, using BFS the path we found was “S – C – E – V” and the length of it is 3. So based on this observation, we could say DFS finds a path but it may or may not be a shorted path from source to target node.
Few of advantages of this approach are,

The fastest way to find a path – it may not be a shortest one.
If the probability of target node exists in the bottom levels. In an organization chart, if we plan to search a less experienced person (hopefully he will be in bottom layers), the DFS will find him faster compared to BFS because it explores the child nodes lot earlier compared to BFS.

DFS implementation
We can implement this in multiple ways. One is using the recursion and other is using Stack data structure. Following is the java implementation of this algorithm.
   public static void graphDFSByRecersion(Node<String> currentNode) {
    if (null == currentNode) {
      return; // back track
    }
    visitNode(currentNode);
    currentNode.visited = true;
    //check if we reached out target node
    if (currentNode.equals(targetNode)) {
      return; // we have found our target node V.
    }
    //recursively visit all of unvisited neighbors
    for (Node<String> neighbor : currentNode.neighbors) {
      if (!neighbor.visited) {
        graphDFSByRecersion(neighbor);
      }
    }
  }

  public static void graphDFSByStack(Node<String> source) {
    //if empty graph, return
    if (null == source) {
      return; //
    }
    Stack<Node<String>> stack = new Stack<Node<String>>();
    //add source to stack
    stack.push(source);
    while (!stack.isEmpty()) {
      Node<String> currentNode = stack.pop();
      visitNode(currentNode);
      currentNode.visited = true;
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //add all of unvisited nodes to stack
      for (Node<String> neighbor : currentNode.neighbors) {
        if (!neighbor.visited) {
          stack.push(neighbor);
        }
      }
    }
  }

  public static void treeDFSByRecersion(Node<String> currentNode) {
    if (null == currentNode) {
      return; // back track
    }
    visitNode(currentNode);
    //check if we reached out target node
    if (currentNode.equals(targetNode)) {
      return; // we have found our target node V.
    }
    //recursively visit all of unvisited neighbors
    for (Node<String> neighbor : currentNode.neighbors) {
              graphDFSByRecersion(neighbor);
    }
  }

  public static void treeDFSByStack(Node<String> source) {
    //if empty graph, return
    if (null == source) {
      return; //
    }
    Stack<Node<String>> stack = new Stack<Node<String>>();
    //add source to stack
    stack.push(source);
    while (!stack.isEmpty()) {
      Node<String> currentNode = stack.pop();
      visitNode(currentNode);
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //add all of unvisited nodes to stack
      for (Node<String> neighbor : currentNode.neighbors) {
          stack.push(neighbor);
      }
    }
  }

Following is the full sample code in Java and you can download and play with the code.
package com.sada.graph;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

//@author Sada Kurapati <sadakurapati@gmail.com>
public class GraphTraversals {

  public static final Node<String> targetNode = new Node<String>("V");
  public static final Node<String> targetTreeNode = new Node<String>("D");

  public static void main(String args[]) {
    //build sample graph.
    Node<String> source = getSampleGraph();
    Node<String> root = getSampleTree();
    //graphBFSByQueue(source);
    //graphBFSByLevelList(source);
    //treeBFSByQueue(root);
    //treeBFSByLevelList(root);
    //graphDFSByRecersion(source);
    //graphDFSByRecersion(source);
    //treeDFSByRecersion(root);
    treeDFSByStack(root);

  }

  public static void graphBFSByQueue(Node<String> source) {
    //if empty graph, then return.
    if (null == source) {
      return;
    }
    Queue<Node<String>> queue = new LinkedList<Node<String>>();
    //add source to queue.
    queue.add(source);
    visitNode(source);
    source.visited = true;
    while (!queue.isEmpty()) {
      Node<String> currentNode = queue.poll();
      //check if we reached out target node
      if (currentNode.equals(targetNode)) {
        return; // we have found our target node V.
      }
      //Add all of unvisited neighbors to the queue. We add only unvisited nodes to avoid cycles.
      for (Node<String> neighbor : currentNode.neighbors) {
        if (!neighbor.visited) {
          visitNode(neighbor);
          neighbor.visited = true; //mark it as visited
          queue.add(neighbor);
        }
      }
    }
  }

  public static void graphBFSByLevelList(Node<String> source) {
    //if empty graph, then return.
    if (null == source) {
      return;
    }
    Set<Node<String>> frontier = new HashSet<Node<String>>();
    //this will be useful to identify what we visited so far and also its level
    //if we dont need level, we could just use a Set or List
    HashMap<Node<String>, Integer> level = new HashMap<Node<String>, Integer>();
    int moves = 0;
    //add source to frontier.
    frontier.add(source);
    visitNode(source);
    level.put(source, moves);
    while (!frontier.isEmpty()) {
      Set<Node<String>> next = new HashSet<Node<String>>();
      for (Node<String> parent : frontier) {
        for (Node<String> neighbor : parent.neighbors) {
          if (!level.containsKey(neighbor)) {
            visitNode(neighbor);
            level.put(neighbor, moves);
            next.add(neighbor);
          }
          //check if we reached out target node
          if (neighbor.equals(targetNode)) {
            return; // we have found our target node V.
          }
        }//inner for
      }//outer for
      moves++;
      frontier = next;
    }//while
  }

  public static void treeBFSByQueue(Node<String> root) {
    //if empty graph, then return.
    if (null == root) {
      return;
    }
    Queue<Node<String>> queue = new LinkedList<Node<String>>();
    //add root to queue.
    queue.add(root);
    while (!queue.isEmpty()) {
      Node<String> currentNode = queue.poll();
      visitNode(currentNode);
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //Add all of unvisited neighbors to the queue. We add only unvisited nodes to avoid cycles.
      for (Node<String> neighbor : currentNode.neighbors) {
        queue.add(neighbor);
      }
    }
  }

  public static void treeBFSByLevelList(Node<String> root) {
    //if empty graph, then return.
    if (null == root) {
      return;
    }
    List<Node<String>> frontier = new ArrayList<Node<String>>();
    //add root to frontier.
    frontier.add(root);
    while (!frontier.isEmpty()) {
      List<Node<String>> next = new ArrayList<Node<String>>();
      for (Node<String> parent : frontier) {
        visitNode(parent);
        //check if we reached out target node
        if (parent.equals(targetTreeNode)) {
          return; // we have found our target node V.
        }

        for (Node<String> neighbor : parent.neighbors) {
          next.add(neighbor);
        }//inner for
      }//outer for
      frontier = next;
    }//while
  }

  public static void graphDFSByRecersion(Node<String> currentNode) {
    if (null == currentNode) {
      return; // back track
    }
    visitNode(currentNode);
    currentNode.visited = true;
    //check if we reached out target node
    if (currentNode.equals(targetNode)) {
      return; // we have found our target node V.
    }
    //recursively visit all of unvisited neighbors
    for (Node<String> neighbor : currentNode.neighbors) {
      if (!neighbor.visited) {
        graphDFSByRecersion(neighbor);
      }
    }
  }

  public static void graphDFSByStack(Node<String> source) {
    //if empty graph, return
    if (null == source) {
      return; //
    }
    Stack<Node<String>> stack = new Stack<Node<String>>();
    //add source to stack
    stack.push(source);
    while (!stack.isEmpty()) {
      Node<String> currentNode = stack.pop();
      visitNode(currentNode);
      currentNode.visited = true;
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //add all of unvisited nodes to stack
      for (Node<String> neighbor : currentNode.neighbors) {
        if (!neighbor.visited) {
          stack.push(neighbor);
        }
      }
    }
  }

  public static void treeDFSByRecersion(Node<String> currentNode) {
    if (null == currentNode) {
      return; // back track
    }
    visitNode(currentNode);
    //check if we reached out target node
    if (currentNode.equals(targetNode)) {
      return; // we have found our target node V.
    }
    //recursively visit all of unvisited neighbors
    for (Node<String> neighbor : currentNode.neighbors) {
              graphDFSByRecersion(neighbor);
    }
  }

  public static void treeDFSByStack(Node<String> source) {
    //if empty graph, return
    if (null == source) {
      return; //
    }
    Stack<Node<String>> stack = new Stack<Node<String>>();
    //add source to stack
    stack.push(source);
    while (!stack.isEmpty()) {
      Node<String> currentNode = stack.pop();
      visitNode(currentNode);
      //check if we reached out target node
      if (currentNode.equals(targetTreeNode)) {
        return; // we have found our target node V.
      }
      //add all of unvisited nodes to stack
      for (Node<String> neighbor : currentNode.neighbors) {
          stack.push(neighbor);
      }
    }
  }

  public static void visitNode(Node<String> node) {
    System.out.printf(" %s ", node.data);
  }

  public static Node<String> getSampleGraph() {
    //building sample graph.
    Node<String> S = new Node<String>("S");
    Node<String> A = new Node<String>("A");
    Node<String> C = new Node<String>("C");
    Node<String> B = new Node<String>("B");
    Node<String> D = new Node<String>("D");
    Node<String> E = new Node<String>("E");
    Node<String> F = new Node<String>("F");
    Node<String> V = new Node<String>("V");

    S.neighbors.add(A);
    S.neighbors.add(C);

    A.neighbors.add(S);
    A.neighbors.add(B);

    B.neighbors.add(A);

    C.neighbors.add(S);
    C.neighbors.add(D);
    C.neighbors.add(E);

    D.neighbors.add(C);
    D.neighbors.add(E);
    D.neighbors.add(F);

    E.neighbors.add(C);
    E.neighbors.add(D);
    E.neighbors.add(F);
    E.neighbors.add(V);

    F.neighbors.add(D);
    F.neighbors.add(E);
    F.neighbors.add(V);

    V.neighbors.add(E);
    V.neighbors.add(F);

    return S;
  }

  public static Node<String> getSampleTree() {
    //building sample Tree.
    Node<String> A = new Node<String>("A");
    Node<String> B = new Node<String>("B");
    Node<String> C = new Node<String>("C");
    Node<String> D = new Node<String>("D");
    Node<String> E = new Node<String>("E");
    Node<String> F = new Node<String>("F");
    Node<String> G = new Node<String>("G");
    Node<String> H = new Node<String>("H");

    A.neighbors.add(B);
    A.neighbors.add(C);
    A.neighbors.add(D);

    B.neighbors.add(E);
    B.neighbors.add(F);
    B.neighbors.add(G);

    C.neighbors.add(H);

    return A;
  }

}

class Node<T> {

  T data;
  ArrayList<Node<T>> neighbors = null;
  boolean visited = false;

  Node(T value) {
    data = value;
    neighbors = new ArrayList<Node<T>>();
  }

  @Override
  public int hashCode() {
    int hash = 5;
    return hash;
  }

  @Override
  public boolean equals(Object obj) {
    if (obj == null) {
      return false;
    }
    if (getClass() != obj.getClass()) {
      return false;
    }
    final Node<?> other = (Node<?>) obj;
    if (this.data != other.data && (this.data == null || !this.data.equals(other.data))) {
      return false;
    }
    return true;
  }
}

			

			
						

Algorithm – Tower of Hanoi Game with K Towers

The standard Tower of Hanoi game is with 3 towers and we need to move all discs from one tower to another. This post provides a flavor of same puzzle but with more than 3 towers and given an initial configuration, we need to find the minimum moves required to go to a target configuration.

Problem

We will be given the discs with radius 1 to N, towers (K), an initial configuration and target configuration. We need to calculate the minimum number of moves we need to make to get to the target configuration starting from initial configuration.

Few rules:

• N discs – there are N discs each with radius of 1 to N
• K towers
• Disc with radius R can be added to the tower if and only if it is empty or the top disc’s radius is < R
• 1<= N<=8 and 3<= K<=5 – these constraints help us in building a more practical algorithm
• Read the input from STDIN – System.in and print the output to STDOUT – System.out

Input format

• First line consists of two integers N and K with space delimited
• 2^nd line consists of initial configuration. It is provided as space delimited integers where index is the disc radius and the number at that index is the tower it contains
• 3^rd line consists of target or desired configuration. It is provided in the same initial configuration.

Sample Input

6 4
4 2 4 3 1 1
1 1 1 1 1 1
Here,

• N=6 (discs) and K=4 (towers)
• Initial configuration is “4 2 4 3 1 1”
  • Tower 1 have 6 and 5 discs
  • Tower 2 have disc 2
  • Tower 3 have disc 4
  • tower 4 have 3 and 1 discs
• Target configuration is “1 1 1 1 1 1”
  •  all discs from 6 to 1 are on tower 1

Following diagram depicts the source and target Tower of Hanoi configurations. Note that the discs are not according to the radius, but they are color coded to represent appropriate radius for simplicity.

Output format

• 1^st line should be the minimum number of moves required to get to target configuration from initial configuration
• From 2^nd line, print from and to tower for a given move. “4 3”  – means a disc is moved from 4^th tower to 3^rd tower

Sample output

Following is the output for above given sample input.
5
3 1
4 3
4 1
2 1
3 1
Here,

• 5 – minimum number of move to get to target configuration
• Then each line consists of from and to towers for each of those 5 moves. For example, “3 1” represents a disc is moved from tower 3 to 1

Solution

There are different ways to solve this problem. Here we will discuss a simple and object oriented approach. We can model this solution as follows.

• This can be solved using a Breadth-First-Search (BFS). Why BFS? It is the best way to travel a level by level and find the shortest path from a given node to target node
• Consider the initial configuration as the starting node
• Then get all of its neighboring nodes – all possible legal configuration we can get from current configuration and repeat this step until we reach target configuration or the graph is exhausts
• Towers can be easily represent as a Stack
• Node contains K towers – it represents a configuration

In Java

Following is the full java implementation of the above approach. Please leave your feedback in comments section.

package com.sada.puzzles;

import com.sada.puzzles.TOH.Node.Move;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;

/**
 *
 * @author Sada Kurapati <sadakurapati@gmail.com>
 */
public class TOH{

  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    //towers initial config
    Node source = readPegsConfiguration(k, n, sc);
    //read target configuration
    Node target = readPegsConfiguration(k, n, sc);
    //To keep track what config we visited and avoid cycles
    Set visited = new HashSet();
    try {
      minMovesToTarget(source, target, visited);
    } catch (Exception ex) {
      System.out.println("Exception = " + ex);
    }
  }

  private static void minMovesToTarget(Node source, Node target, Set visited) throws CloneNotSupportedException {
    //Perform BFS
    //add source node to Queue
    Queue q = new LinkedList();
    q.add(source);
    Node current = source;
    while (!q.isEmpty()) {
      current = q.poll();
      if (current.equals(target)) { //found the target configuration
        break;
      }
      List neighbors = current.neighbors();
      if (neighbors.size() > 0) {
        for (Node n : neighbors) {
          if (!visited.contains(n)) {//if not visited, put it in queue
            q.offer(n);
            visited.add(n);
          }
        }
      }
    }
    //Printing path and moves if target config found
    if (current.equals(target)) {
      printOutput(current);
    }
  }

  private static Node readPegsConfiguration(int k, int n, Scanner sc) {
    Stack[] initialState = new Stack[k];
    for (int i = 0; i < k; i++) {
      initialState[i] = new Stack();
    }
    //reading and reversing the line as we need to put the elements in decresing size
    //disc is key and tower is value.
    TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
    for (int i = 0; i < n; i++) {
      map.put(i, sc.nextInt());
    }
    //prepare towers
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
      initialState[entry.getValue() - 1].push(entry.getKey());
    }
    return new Node(initialState);
  }

  static void printOutput(Node target) {
    Stack stack = new Stack<>(); //using stack as we need to print the trail from Source - target config
    while (target.parent != null) {
      stack.add(target.move);
      target = target.parent;
    }
    System.out.println(stack.size());
    while (!stack.isEmpty()) {
      System.out.println(stack.pop());
    }
  }

  static class Node implements Cloneable {
    //towers
    Stack[] state = null;
    Node parent = null;  //for backtracking trail
    Move move = null; // The move we made to go to next neighbor config

    public Node(Stack[] st) {
      state = st;
    }

    @Override
    protected Node clone() throws CloneNotSupportedException {
      Stack[] cloneStacks = new Stack[state.length];
      for (int i = 0; i < state.length; i++) {
        cloneStacks[i] = (Stack) state[i].clone();
      }
      Node clone = new Node(cloneStacks);
      return clone;
    }

    //returns the neghboring configurations.
    //What all configurations we can get based on current config.
    public List neighbors() throws CloneNotSupportedException {
      List neighbors = new ArrayList<>();
      int k = state.length;
      for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
          if (i != j && !state[i].isEmpty()) {
            //Need to clone to avoid change the parent node.
            //Hint - in java, objects are not mutable and they are references
            Node child = this.clone();
            //make a move
            if (canWeMove(child.state[i], child.state[j])) {
              child.state[j].push(child.state[i].pop());
              //this is required to backtrack the trail once we find the target config
              child.parent = this;
              //the move we made to get to this neighbor
              child.move = new Move(i, j);
              neighbors.add(child);
            }
          }
        }
      }
      return neighbors;
    }

    public boolean canWeMove(Stack fromTower, Stack toTower) {
      boolean answer = false;
      if (toTower.isEmpty()) {// if destination tower is empty, then we can move any disc
        return true;
      }
      int toDisc = toTower.peek();
      int fromDisc = fromTower.peek();
      if (fromDisc < toDisc) { //we can only place small disc on top
        answer = true;
      }
      return answer;
    }

    @Override
    public int hashCode() {
      int hash = 7;
      return hash;
    }

    @Override
    public boolean equals(Object obj) {
      if (obj == null) {
        return false;
      }
      if (getClass() != obj.getClass()) {
        return false;
      }
      final Node other = (Node) obj;
      if (!Arrays.deepEquals(this.state, other.state)) {
        return false;
      }
      return true;
    }

    class Move {
      int towerFrom, towerTo;
      public Move(int f, int t) {
        towerFrom = f + 1;
        towerTo = t + 1;
      }
     @Override
      public String toString() {
        return towerFrom + " " + towerTo;
      }
    }
  }
}