Please use Java to solve this problem.

3. (25: optional after two required) [Breadth-first search: programming Implement a graph traversal algorithm using the breadth-first search and run the program against the graph shown above in Exercise 1 (left). An adjacency list -- not an adjacency matrix or an edge list -- structured as shown above in Exercise 1 (right) must be used as the data structure of the graph. Use exactly the same order of nodes in each linked list connected to the array of vertices, or your program output may be different. In each run, the program should prompt a screen input of the vertex number (1 to 8) and, once the number is entered, output the vertex number each time a new vertex is visited during the graph traversal. Your program code will be tested for multiple alternative start vertices. Submit the source codes via Blackboard. Program codes should be working and neatly organized and well commented. DFS(u): Depth-first search tree Mark u as "Explored" and add u to T' For each edge (u, v) incident to u If v is not marked "Explored" then Recursively invoke DFS (v) Endif Endfor 4 2 4 4