Repository: TheAlgorithms/Java
File: src/main/java/com/thealgorithms/datastructures/graphs/BipartiteGraphDFS.java (Java)

Code before:

    /**
     * Helper method to perform DFS and check if the graph is bipartite.
     *
     * @param v     Number of vertices in the graph
     * @param adj   Adjacency list of the graph
     * @param color Array to store colors assigned to vertices
     * @param node  Current node being processed
     * @return      True if the graph is bipartite, otherwise false
     */
    private static boolean bipartite(int v, ArrayList<ArrayList<Integer>> adj, int[] color, int node) {
        if (color[node] == -1) {
            color[node] = 1;
        }
        for (Integer it : adj.get(node)) {
            if (color[it] == -1) {
                color[it] = 1 - color[node];
                if (!bipartite(v, adj, color, it)) {
                    return false;
                }
            } else if (color[it] == color[node]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Method to check if the graph is bipartite.
     *
     * @param v   Number of vertices in the graph
     * @param adj Adjacency list of the graph
     * @return    True if the graph is bipartite, otherwise false
     */
    public static boolean isBipartite(int v, ArrayList<ArrayList<Integer>> adj) {
        // Code here
        int[] color = new int[v + 1];
        Arrays.fill(color, -1);
        for (int i = 0; i < v; i++) {
            if (color[i] == -1) {
                if (!bipartite(v, adj, color, i)) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * Main method to read input and check if the graph is bipartite.
     *

Review comment (refactor):
Looks good. But can be improved a bit:

```
/**
 * Helper method to perform DFS and check if the graph is bipartite.
 * 
 * During DFS traversal, this method attempts to color each vertex in such a way 
 * that no two adjacent vertices share the same color.
 *
 * @param v     Number of vertices in the graph
 * @param adj   Adjacency list of the graph where each index i contains a list of adjacent vertices
 * @param color Array to store the color assigned to each vertex (-1 indicates uncolored)
 * @param node  Current vertex being processed
 * @return      True if the graph (or component of the graph) is bipartite, otherwise false
 */
```

Code after:
 * Output: YES (This graph is bipartite)
 *
 * Input (Adjacency Matrix):
 * {{0, 1, 1, 0},
 *  {1, 0, 1, 0},
 *  {1, 1, 0, 1},
 *  {0, 0, 1, 0}}
 *
 * Output: NO (This graph is not bipartite)
 */
public final class BipartiteGraphDFS {
    private BipartiteGraphDFS() {
    }

    /**
     * Helper method to perform DFS and check if the graph is bipartite.
     *
     * During DFS traversal, this method attempts to color each vertex in such a way
     * that no two adjacent vertices share the same color.
     *
     * @param v     Number of vertices in the graph
     * @param adj   Adjacency list of the graph where each index i contains a list of adjacent vertices
     * @param color Array to store the color assigned to each vertex (-1 indicates uncolored)
     * @param node  Current vertex being processed
     * @return      True if the graph (or component of the graph) is bipartite, otherwise false
     */
    private static boolean bipartite(int v, ArrayList<ArrayList<Integer>> adj, int[] color, int node) {
        if (color[node] == -1) {
            color[node] = 1;
        }
        for (Integer it : adj.get(node)) {
            if (color[it] == -1) {
                color[it] = 1 - color[node];
                if (!bipartite(v, adj, color, it)) {
                    return false;
                }
            } else if (color[it] == color[node]) {
                return false;
            }
        }
        return true;
    }

    /**
     * Method to check if the graph is bipartite.
     *
     * @param v   Number of vertices in the graph
     * @param adj Adjacency list of the graph
     * @return    True if the graph is bipartite, otherwise false
     */
    public static boolean isBipartite(int v, ArrayList<ArrayList<Integer>> adj) {