DO NOT COPY CODE FROM THE INTERNET!QUESTION NUMBER 2 from the image: 1. Perform a depth-first search of the Australia digraph given below,starting at Sydney. List the order in which the cities are processed.Do the same for a breadth-first search.PerthCSC 236 Lab 7 (2 programs) graphs15Darwin4BlackStump3Adelaide23CanberraMelbourne2. Consider the graph below. Write a program that outputs the shortestdistance from node 0 to every other node in the graph.8Fly Crocodile AirlinesHobart12BrisbaneSydney

import java.util.*;public class GraphParseClass { /* creating graph with city names */public GraphNode generateGraph() {GraphNode rootNode = new GraphNode("sydney");GraphNode a = new GraphNode("Brisbane");GraphNode b = new GraphNode("Caniberra");GraphNode c = new GraphNode("Adelaide");GraphNode d = new GraphNode("Melbourne");GraphNode e = new GraphNode("Perth");GraphNode f = new GraphNode("Hobart");GraphNode g = new GraphNode("Black stump");GraphNode h = new GraphNode("Darwin");rootNode.left = a;rootNode.right = b;b.left = a;b.right = c;c.left = d;c.right = e;d.left = b;d.right = f;e.left = g;g.left = h;return rootNode;} private GraphNode getUnvisitNode(GraphNode node) {if (node.left != null) {if (!node.left.visited) {return node.left;}}if (node.right != null) {if (!node.right.visited) {return node.right;}}return null;} /* using queue for BFS */public void calculateBFS(GraphNode rootNode) {System.out.println(" BREADTH FIRST SEARCH ");Queue<GraphNode> bfs_queue = new LinkedList<>();bfs_queue.add(rootNode);System.out.println(rootNode.city);while (!bfs_queue.isEmpty()) {GraphNode node = bfs_queue.remove(); // removing top elementGraphNode child = null;while ((child = getUnvisitNode(node)) != null) {child.visited = true;System.out.println(child.city);bfs_queue.add(child);}}} /* using stack for DFS */public void calculateDFS(GraphNode rootNode) {System.out.println("\n DEPTH FIRST SEARCH ");Stack<GraphNode> dfs_stack = new Stack<>();dfs_stack.push(rootNode);rootNode.visited = true;System.out.println(rootNode.city);while (!dfs_stack.isEmpty()) {GraphNode node = dfs_stack.peek(); // getting top element, but not removingGraphNode child = getUnvisitNode(node);if (child != null) {child.visited = true;System.out.println(child.city);dfs_stack.push(child);} else {dfs_stack.pop();}}} private class GraphNode { private String city;private GraphNode left, right;private boolean visited; private GraphNode(String city) {this.city = city;this.left = this.right = null;} }public static void main(String args[]){GraphParseClass obj = new GraphParseClass();GraphNode root = obj.generateGraph();//calling methodsobj.calculateBFS(root);GraphParseClass obj1 = new GraphParseClass();GraphNode root1 = obj1.generateGraph();obj1.calculateDFS(root1);}}2.) for the second question we can use Dijkstraâ€™s shortest path algorithm. Please refer the below java code both the solutions are provided in single java class,Driver program is also provided for testing purpose.Copy and paste the code below in your program editor. For any clarification do let me know in comment section. Thanks. //java program import java.util.LinkedList; /*representing a static graph given as Adjacency List for simplicity*/public class AustraliaGraph { static int V = 6; public static int minDistance(int distance[], boolean sptSet[]) { int min = Integer.MAX_VALUE; int min_index = -1; for (int v = 0; v < V; v++) if (sptSet[v] == false && distance[v] <= min) { min = distance[v]; min_index = v; } return min_index; } public static void printSolution(int dist[], int n) { System.out.println("Vertex Distance from 0"); for (int i = 0; i < V; i++) System.out.println(i + " t " + dist[i]); } public static void dijkstra(int cost[][], int src,LinkedList<Integer>[] graph) { int distance[] = new int[V]; boolean visited[] = new boolean[V]; for (int i = 0; i < V; i++) { distance[i] = Integer.MAX_VALUE; visited[i] = false; } distance[src] = 0; for (int i = 0; i < V - 1; i++) { int u = minDistance(distance, visited); visited[u]=true; for (int v = 0; v < V; v++) if (!visited[v] && cost[u][v] != 0 && distance[u] != Integer.MAX_VALUE && distance[u] + cost[u][v] < distance[v]) distance[v] = distance[u] + cost[u][v]; } // print the constructed distance array printSolution(distance, V); } public static void BFS(LinkedList<Integer>[] graph,int source) { // Create a queue for BFS LinkedList<Integer> queue = new LinkedList<Integer>(); visited[source]=true; queue.add(source); while (queue.size() != 0) { // Dequeue a node and print the city int s = queue.poll(); System.out.print(cites[s]+" "); // Get all adjacent vertices of source // If a adjacent has not been visited, then mark it // visited and enqueue it for (int n:graph[s]) { if (!visited[n]) { visited[n] = true; queue.add(n); } } } } //to keep track for already visited nodes public static boolean[] visited; public static void DFS(LinkedList<Integer>[] graph,int source) { //print current city System.out.println(cites[source]); visited[source]=true; //explore neighbours for(int adj:graph[source]) { //check if already visited if(visited[adj]) { continue; } else { DFS(graph,adj); } } } //for mapping integer values to city name public static String[] cites = {"sydney","hobart","melbourne","canberra","brisbane","adelaide","perth", "Black stump","darwin"}; public static void main(String[] arg) { LinkedList<Integer>[] graph = new LinkedList[9]; for(int i=0;i<9;i++) { graph[i]= new LinkedList<Integer>(); } //adding edges graph[0].add(2); graph[2].add(1); graph[1].add(2); graph[2].add(0); graph[2].add(3); graph[3].add(4); graph[4].add(0); graph[3].add(5); graph[5].add(2); graph[5].add(6); graph[6].add(7); graph[7].add(8); graph[8].add(3); //intialize visited by false visited = new boolean[9]; System.out.println("Output from depth first search"); DFS(graph,0); visited = new boolean[9]; System.out.println("Output from breadth first search"); BFS(graph,0); //for 2nd question we need to create two lists one for adjacency and second for cost. LinkedList<Integer>[] graphForShortestPath = new LinkedList[9]; for(int i=0;i<6;i++) { graphForShortestPath[i]= new LinkedList<Integer>(); } graphForShortestPath[0].add(1); graphForShortestPath[0].add(3); graphForShortestPath[0].add(2); graphForShortestPath[1].add(2); graphForShortestPath[1].add(5); graphForShortestPath[1].add(4); graphForShortestPath[2].add(4); graphForShortestPath[4].add(2); graphForShortestPath[4].add(5); graphForShortestPath[5].add(3); //if there is no cost between two nodes then cost will be 0 that means no edge int m = 0; int[][] cost={{0,3,15,3,0,0},{0,0,5,0,8,12},{0,0,0,0,2,0},{0,0,0,0,0,0},{0,0,3,0,0,8},{0,0,0,7,0,0}}; dijkstra(cost,0,graphForShortestPath); }}I hope you got your answer :)