Write code in java and answer a and b$.$ Problem $2.$ Design two algorithms, one using breadth$-$first search $($BFS$)$ and the other using depth$-$first

search $($DFS$),$ to determine whether an input graph is $2-$colorable. A graph is called $2-$colorable $($or

bipartite$)$ if all its vertices can be colored using two different colors such that every edge has its two

endpoints colored in different colors. For instance, the graph shown in Figure $($a$)$ below is a $2-$colorable

graph and Figure $($b$)$ illustrates a valid coloring of it$,$ while the graph shown in Figure $($c$)$ is not $2-$colorable.

To determine whether a graph is $2-$colorable, you can try to color the vertices using two colors, say, red

and blue, in an alternating fashion as you traverse the graph using BFS or DFS$.$ In other words, when you

visit an unvisited vertex, assign it the color that differs from its parent's color in the breadth$/$depth$-$first

tree. When you encounter an edge that has its two endpoints already assigned the same color, you can

terminate the algorithm and conclude that the input graph is not $2-$colorable.

Please use adjacency lists to represent the input graph. For each algorithm, your program will output

the following:

$(1)$ The number of vertices and the number of edges of the input graph:

$(2)$ A table of $$ values $($predecessor$/$parent in the breadth$/$depth$-$first tree$)$ of all visited vertices:

$(3)$ A sentence that tells whether or not the input graph is $2-$colorable:

$(4)-$ If the graph is $2-$colorable, output a valid coloring including the label and the color of each

vertex. Here is an example output of a valid coloring for the graph shown in Figure $($a$)$:

a$($blue$),$ b$($red$),$ c$($blue$),$ f$($red$),$ e$($blue$),$ d$($red$)$

If the graph is not $2-$colorable, output a list of vertices that have already been visited along

with their assigned colors. Additionally, please also output the detected edge that has its two

endpoints assigned the same color. For example, if the graph shown in Figure $($c$)$ is represented

using the following adjacency lists,

$a,bcd$

$b,ad$

$c,ad$

$d,abc$

here is an example output of a partial coloring and the edge whose two endpoints have already

been assigned the same color.

When BFS is applied:

a$($blue$),$ b$($red$),$ c$($red$),$ d$($red$)$

The two endpoints of edge $($b$,$ d$)$ are both red.

When DFS is applied:

a$($blue$),$ b$($red$),$ d$($blue$)$

The two endpoints of edge $(d,a)$ are both blue.

Complete the Following Tasks:

a$.$ Programming. Submit one $.$zip file including all source files of your program for grading. $|$

$3$

b$.$ Run your program on the following two graphs using the corresponding adjacency lists shown

below and insert screenshots of your program's output for each graph. For each graph,

$(1)$ Draw the breadth$-$first tree and the depth$-$first tree using the $$ values from your program's autput:

$(2)$ Specify the color assigned to each vertex based on the coloring output by your program for both BFS

and DFS$.$

If the graph is not $2-$colorable, you only need to draw part of the tree for the vertices that have already

been visited along with their assigned colors; for each algorithm, highlight the detected edge that has its

two endpoints assigned the same color. You will not get full credits for both parts a and $b$ if any part of

your program's output for these two graphs is incorrect.