q1 q2 q3

//1st question
class Graph {

    int N; // No. of vertices
    LinkedList<Integer> adjListArray[]; // To store a adjacency list

    // Initialize a graph
    Graph(int nodes) {
        this.N = nodes;

        adjListArray = new LinkedList[nodes];

        int i = 0;
        while (i < nodes) {
            adjListArray[i] = new LinkedList<>();

            i++;
        }

        // YOUR CODE HERE

    }

    // Adds an edge from a source vertex to a desctination vertex
    void addEdge(int src, int dest) {
        // YOUR CODE HERE
        adjListArray[src].add(dest);

    }

    // A method to print the adjacency list
    void printGraph(Graph graph) {
        // YOUR CODE HERE
        int j = 0;
        while (j < graph.N) {
            if(adjListArray[j].size() == 0){
                System.out.print("No vertex found");
            }

            else {
                int i = 0;
                String vert = "";
                while(i < graph.adjListArray[j].size()){
                    vert += + graph.adjListArray[j].get(i) + ",";
                    i++;
                }
                System.out.println("Adjacency list of vertex "+ j +": " + vert.substring(0, vert.length() -1));

            }



                System.out.println("");
                j++;
            }



        }

    }
//2nd question
class GraphTraversal {
    private int V; // No. of vertices
    private LinkedList<Integer> adj[]; // To store a adjacency list

    /*
     * Initialize a graph
     */
    GraphTraversal(int v) {
        // YOUR CODE HERE
        V = v;
        adj = new LinkedList[v];
        int i = 0;
        while( i < v) {
            adj[i] = new LinkedList();
            i++;
        }

    }

    /*
     * Add an edge into a graph
     */
    void addEdge(int v, int w) {
        // YOUR CODE HERE
        adj[v].add(w);
    }

    /*
     * This mehtod is to calculate and show the shortest path from a given
     * vertex
     */
    void shortestPath(int start) {
        // YOUR CODE HERE

        boolean[] visited = new boolean[V];

        LinkedList<Integer> q = new LinkedList<>();
        LinkedList<Integer> current = new LinkedList<>();

        current.add(start);
        q.add(start);

        visited[start] = true;
        for (int parts = 0; !q.isEmpty(); parts++) {
            for (int i = 0; !q.isEmpty(); i++) {

                System.out.println("Distance from vertex 2 to vertex " + q.peek() + " is: " + parts);
                q.remove();
            }

            for (int j = 0; !current.isEmpty(); j++) {
                int k = 0;
                while (k < adj[current.getFirst()].size()) {
                    if (visited[adj[current.getFirst()].get(k)] != true) {
                        q.add(adj[current.getFirst()].get(k));
                        visited[adj[current.getFirst()].get(k)] = true;

                    }
                    k++;

                }

                current.remove();

            }

            Iterator<Integer> it = q.iterator();
            for (int s = 0; it.hasNext(); s++) {
                current.add(it.next());

            }

        }
    }
}
//3rd question
GraphTraversalDFS(int v) {
        // YOUR CODE HERE
        V = v;
        adj = new LinkedList[v];
        int i = 0;
        while (i < v) {
            adj[i] = new LinkedList();
            i++;
        }

    }

    /*
     * Add an edge into a graph
     */
    void addEdge(int v, int w) {
        // YOUR CODE HERE
        adj[v].add(w);

    }

    /*
     * Method to traverse the graph with DFS Suggestion: write recursive DFS
     */
    void DFS(int v, boolean visited[]) {
        // YOUR CODE HERE
        Stack<Integer> stack = new Stack<Integer>();
        visited[v] = true;

        int currentVert = v;
        stack.push(v);

        int currentNodes = 1;

        LinkedList<Integer> firstNodes = new LinkedList<>();

        firstNodes.add(v);
        int nodes;
        for (nodes = 1; !stack.isEmpty(); nodes++) {
            stack.pop();
            int i = 0;
            while (i < adj[currentVert].size()) {
                if (visited[adj[currentVert].get(i)] != true) {
                    stack.push(adj[currentVert].get(i));
                    visited[adj[currentVert].get(i)] = true;
                }
                i++;
            }
            if (!stack.isEmpty()) {
                currentVert = stack.peek();
            } else {
                int j = 0;
                while (j < visited.length) {
                    if (visited[j] != true) {
                        stack.push(j);
                        currentVert = j;
                        currentNodes++;
                        firstNodes.add(j);
                        visited[j] = true;
                        break;
                    }
                    j++;
                }
            }
        }
        System.out.println("You can traverse the entire graph by selecting " + currentNodes + " starting vertices");
        System.out.println("Starting vertices are: " + firstNodes);
    }

    /*
     * Method to calculate the number of starting nodes
     */
    void countStartingNodes() {
        // YOUR CODE HERE
        boolean visited[] = new boolean[V];

        // Call the recursive helper function to print DFS traversal
        // starting from all vertices one by one

        DFS(0, visited);
        // Call DFS HERE

        // Call the recursive helper function to print DFS traversal

    }
}