Bidirectional Searching Graph Algorithm

Bidirectional Search

We know our traditional searching algorithms to search for a goal vertex starting from a source
vertex  using BFS.In normal graph search using BFS/DFS we begin our search in one direction usually from source vertex toward the goal vertex, but what if we start search form both direction simultaneously.

So , Bidirectional search is a graph searching algorithm which find shortest path from source to goal vertex. It runs two simultaneous search that is.

1)Forward search form source/initial vertex toward goal vertex
2)Backward search form goal/target vertex toward source vertex

Bidirectional search replaces single search graph which is likely to grow exponentially with two smaller sub graphs – one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs reach at same point or intersect each-other.

For Example:

Suppose we want to find if there exists a path from vertex 0 to vertex 14. Here we can execute two searches, one from vertex 0 and other from vertex 14. When both forward and backward search meet at vertex 7, we know that we have found a path from node 0 to 14 and search can be terminated now. We can clearly see that we have successfully avoided unnecessary exploration.


Now Question is why bidirectional approach?

Ans: Because

1)in many cases it is faster.

2)It dramatically reduce the amount of required exploration.

Let us suppose,

 if branching factor of tree is a and distance of goal vertex from source is d,
 then the normal BFS/DFS searching complexity would be O(a^d).

On the other hand, if we execute two search operation then the complexity would be O(a^{d/2})
for each search and total complexity would be O(a^{d/2}+a^{d/2}) which is far less than O(a^d).

When to use bidirectional approach?

1)Both initial and goal states are unique and completely defined.
The branching factor is exactly the same in both directions.

Performance measures

Completeness : Bidirectional search is complete if BFS is used in both searches.

Optimality : It is optimal if BFS is used for search and paths have uniform cost.
Time and Space Complexity : Time and space complexity is O(a^{d/2})

Sample Code:

public static class Node
{
    private final T data;
    private final Set<Node> adjacent = new HashSet<Node>();

    public Set<Node> getAdjacent() {
      return adjacent;
    }

    public Node(T data) {
      this.data = data;
    }

    public T getData() {
      return data;
    }

    // returns if the node was added, false if already there
    public boolean addAdjacent(Node node) {
      return adjacent.add(node);
    }

    // returns true if any were added
    public boolean addAdjacents(Set<Node> nodes) {
      return adjacent.addAll(nodes);
    }
}

public static boolean pathExistsBidirectional(Node a, Node b)
{
    // BFS on both nodes at the same time
    Queue<Node> queueA = new Queue<Node>();
    Queue<Node> queueB = new Queue<Node>();
    Set<Node> visitedA = new HashSet<Node>();
    Set<Node> visitedB = new HashSet<Node>();

    visitedA.add(a);
    visitedB.add(b);
    queueA.add(a);
    queueB.add(b);

    while (!queueA.isEmpty() && !queueB.isEmpty()) {
      if (pathExistsBidirectionalHelper(queueA, visitedA, visitedB)) {
        return true;
      }
      if (pathExistsBidirectionalHelper(queueB, visitedB, visitedA)) {
        return true;
      }
    }

    return false;
  }

  private static boolean pathExistsBidirectionalHelper(Queue<Node> queue, Set<Node> visitedFromThisSide, Set<Node> visitedFromThatSide) {
    if (!queue.isEmpty()) {
      Node next = queue.remove();
      for (Node adjacent : next.getAdjacent()) {
        if (visitedFromThatSide.contains(adjacent)) {
          return true;
        } else if (visitedFromThisSide.add(adjacent)) {
          queue.add(adjacent);
        }
      }
    }
    return false;
  }



 

Noble integers in an array or count of greater elements is equal to value java

Noble integers in an array or count of greater elements is equal to value?.

Explanation:

Given an array arr[], find a Noble integer in it. An integer x is said to be Noble in arr[] if the number of integers greater than x are equal to x. If there are many Noble integers, return any of them. If there is no, then return -1.

Examples:

Input  : [7, 3, 16, 10]
Output : 3
Number of integers greater than 3 is three.

Input  : [-1, -9, -2, -78, 0]
Output : 0
Number of integers greater than 0 is zero.

Solution:

There can be many approach to solve this problem.you can solve this problem by "Brute Force" approach and also by
"Sorting" .

Brute Force Approach:

First Step: Iterate through the array.
Second Step: For every element arr[i], find the number of elements greater than arr[i].

Sample Program:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NobleIntegerApp
{

public static void main(String[] args)
{
int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);
       
        if (res!=-1)
            System.out.println("The noble integer is "+ res);
        else
            System.out.println("No Noble Integer Found");
}

public static int nobleInteger(int arr[])
       {
        int size = arr.length;
        for (int i=0; i<size; i++ )
        {
            int count = 0;
            for (int j=0; j<size; j++)
                if (arr[i] < arr[j])
                    count++;
           
            if (count == arr[i])
                return arr[i];
        }
        return -1;
    }

}

 Output:The noble integer is 3

Complexity: Though this is not very good Solution as you can see there are two loops and comparison happening.

Sorting Approach:

Step one: Sort the array in ascending order.complexity O(nlogn).
Step two:Iterate through the array.
Step three: Compare the value of index i to the number of elements after index i.
           If arr[i] equals the number of elements after arr[i], it is a noble Integer.

Step four:Check condition, (A[i] == length-i-1). the complexity in doing this would be O(n).

Sample Code:

/**
 *
 */

/**
 * @author Abhinaw.Tripathi
 *
 */
public class NobleIntegerApp
{

public static void main(String[] args)
{
int [] arr = {10, 3, 20, 40, 2};

        int res = nobleInteger(arr);
       
        if (res!=-1)
            System.out.println("The noble integer is "+ res);
        else
            System.out.println("No Noble Integer Found");
}

public static int nobleInteger(int arr[])
      {
 Arrays.sort(arr);
       int n = arr.length;
       for (int i=0; i<n-1; i++)
       {
           if (arr[i] == arr[i+1])
               continue;

           if (arr[i] == n-i-1)
               return arr[i];
       }

       if (arr[n-1] == 0)
           return arr[n-1];

       return -1;
    }

}


Output: The noble integer is 3