Lab 2: Search algorithm

//========= Node.java file ==================
public class Node {
    int id;
    String name;
    boolean visited;

    public Node(int id,String name){
        this.id = id;
        this.name = name;
        this.visited = false;
    }

    public String getName(){
        return name;
    }
}

// ============ Node.java file code end ==========


// ============ Graph.java file ===================
import java.util.HashMap;
import java.util.LinkedList;

public class Graph {
    
    HashMap<Node,LinkedList<Node>> adjancencyMap = new HashMap<Node,LinkedList<Node>>();
    boolean directed;

    public void insertEdge(Node source, Node neighbour){
        LinkedList<Node> tmp = new LinkedList<Node>();
        tmp.add(neighbour);
        if(adjancencyMap.isEmpty()) adjancencyMap.put(source, tmp); 

        else if(!adjancencyMap.keySet().contains(source)){
            
            adjancencyMap.put(source, tmp);
        }
        else{
            adjancencyMap.get(source).add(neighbour);
        }

    } 

    public void printEdges(Node startingNode){
       LinkedList<Node> neighbours =  adjancencyMap.get(startingNode);
       System.out.println("The neighbour city of "+startingNode.getName()+" are:");
       for(Node node: neighbours){
            System.out.println(node.getName());
       }
        
    }

    public void DFS(Node startingNode){
        startingNode.visited = true;
        LinkedList<Node> neighbours =  adjancencyMap.get(startingNode);
        for(Node node: neighbours){
            if(!node.visited){
                System.out.println(node.getName());
                DFS(node);
            }
        }
    }
    public void BFS(Node startingNode){
        LinkedList<Node> q = new LinkedList<Node>();
       
        q.add(startingNode);
        while(!q.isEmpty()){
           Node neigh = q.removeFirst();
           if(!neigh.visited) neigh.visited = true;
           LinkedList<Node> neighbours =  adjancencyMap.get(neigh);
           for(Node node: neighbours){
            if(!node.visited && !q.contains(node)){
                System.out.println(node.getName());
                q.add(node);
            }
           }
        }

    }

    public Node BestFirstSearch(Node start, Node destination){
        LinkedList<Node> closedList = new LinkedList<Node>();
        LinkedList<Node> openedList = new LinkedList<Node>();
        openedList.add(start);

        while(!openedList.isEmpty()){
            Node first_node = openedList.removeFirst();
            LinkedList<Node> neighbours =  adjancencyMap.get(first_node);
            if(first_node.equals(destination)){
                System.out.println(first_node.getName());
                return first_node;
            }
            System.out.print(first_node.getName()+" -> ");
            for(Node node: neighbours ){
                if(!openedList.contains(node) && !closedList.contains(node)){
                    openedList.addFirst(node);
                    openedList.add(node);
                   
                }
            }
            openedList.remove(first_node);
            closedList.add(first_node);
        }

        return start;

    }
}

// =========== Graph.java file code end =================


// =========== Search.java file ========================

public class Search{
    public static void main(String[] args){
        Node n1 = new Node(1,"Arad");
        Node n2 = new Node(2, "Bucharest");
        Node n3 = new Node(3, "Craiva");
        Node n4 = new Node(4, "Dobreta");
        Node n5 = new Node(5, "Eforia");
        Node n6 = new Node(6, "Fagaras");
        Node n7 = new Node(7, "Giurgiu");
        Node n8 = new Node(8, "Hirsova");
        Node n9 = new Node(9, "Lasi");
        Node n10 = new Node(10, "Lugoj");
        Node n11 = new Node(11, "Mehadia");
        Node n12 = new Node(12, "Neamt");
        Node n13 = new Node(13, "Oradea");
        Node n14 = new Node(14, "Pitesti");
        Node n15 = new Node(15, "Rimnicu Vilcea");
        Node n16 = new Node(16, "Sibiu");
        Node n17 = new Node(17, "Timisoara");
        Node n18 = new Node(18, "Urziceni");
        Node n19 = new Node(19, "Vaslui");
        Node n20 = new Node(20, "Zerind");

        Graph g = new Graph();
        g.insertEdge(n1, n13);
        g.insertEdge(n1, n16);
        g.insertEdge(n1,n17);
        g.insertEdge(n2,n7);
        g.insertEdge(n2, n14);
        g.insertEdge(n2, n18);
        g.insertEdge(n2, n6);
        g.insertEdge(n3,n4);
        g.insertEdge(n3, n14);
        g.insertEdge(n3, n15);
        g.insertEdge(n4, n3);
        g.insertEdge(n4,n11);
        g.insertEdge(n5, n8);
        g.insertEdge(n6,n16);
        g.insertEdge(n6,n2);
        g.insertEdge(n7,n2);
        g.insertEdge(n8, n18);
        g.insertEdge(n8,n5);
        g.insertEdge(n9,n12);
        g.insertEdge(n9,n19);
        g.insertEdge(n10,n11);
        g.insertEdge(n10,n17);
        g.insertEdge(n11, n4);
        g.insertEdge(n11, n10);
        g.insertEdge(n12, n9);
        g.insertEdge(n13, n16);
        g.insertEdge(n13, n20);
        g.insertEdge(n14, n15);
        g.insertEdge(n14, n3);
        g.insertEdge(n14, n2);
        g.insertEdge(n15, n16);
        g.insertEdge(n15, n3);
        g.insertEdge(n15, n14);
        g.insertEdge(n16, n1);
        g.insertEdge(n16, n6);
        g.insertEdge(n16, n15);
        g.insertEdge(n16, n13);
        g.insertEdge(n17, n1);
        g.insertEdge(n17, n10);
        g.insertEdge(n18, n2);
        g.insertEdge(n18, n8);
        g.insertEdge(n18, n19);
        g.insertEdge(n19,n9);
        g.insertEdge(n19, n18);
        g.insertEdge(n20, n1);
        g.insertEdge(n20, n13);

        g.printEdges(n1);

        // Depth-First Search
        g.DFS(n1);

        // Breadth-First Search
        g.BFS(n1);

        // Best-First Search
        g.BestFirstSearch(n1, n2);
       
    }
}

// ============= Search.java file code end ===============