Java Assignment Assume you have a graph G V E adjacency mat

Java Assignment

Assume you have a graph G = (V, E) (adjacency matrix or adjacency list). Also assume all the weights of the graphs are same. Now use BFS to find the shortest path between source and destination. User can input source and destination.

Solution

Program :

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Node {

    public String nodeName;
    Node leftChild;
    Node rightChild;

    public Node(String nodename, Node firstChild, Node secondChild){
        this.nodename = nodename;
        this.leftChild = firstChild;
        this.rightChild = secondChild;
    }

    public ArrayList<node> getChildren(){
        ArrayList<node> childNodes = new ArrayList<>();
        if(this.leftChild != null)
        {
            childNodes.add(leftChild);
        }
        if(this.rightChild != null) {
            childNodes.add(rightChild);
        }
        return childNodes;
    }

    public boolean removeChild(Node n){
        return false;
    }

}

/**
* breadth first search
*/
public class BreadthFirstSearch {

    Node startNode;
    Node goalNode;

    public BreadthFirstSearch(Node start, Node goalNode){
        this.startNode = start;
        this.goalNode = goalNode;
    }

    public boolean compute(){

        if(this.startNode.equals(goalNode)){
            System.out.println(\"Goal Node Found!\");
            System.out.println(startNode);
        }

        Queue<node> queue = new LinkedList<>();
        ArrayList<node> explored = new ArrayList<>();
        queue.add(this.startNode);
        explored.add(startNode);

        while(!queue.isEmpty()){
            Node current = queue.remove();
            if(current.equals(this.goalNode)) {
                System.out.println(explored);
                return true;
            }
            else{
                if(current.getChildren().isEmpty())
                    return false;
                else
                    queue.addAll(current.getChildren());
            }
            explored.add(current);
        }

        return false;

    }

}

public class Driver {

    public static void main(String args[]){
        Node station1 = new Node(\"1\", 2, 5);
        Node station2 = new Node(\"2\", 3, 5);
        Node station3 = new Node(\"3\", 2, 4);
        Node station4 = new Node(\"4\", 5, 6);
        Node station5 = new Node(\"5\", 1, 4);
        Node station6 = new Node(\"6\", null, null);

        BreadthFirstSearch bfs = new BreadthFirstSearch(1, 6);

        if(bfs.compute())
            System.out.print(\"Path Found!\");
    }
}