JavaScript Coding Test Course, Determine Bipartite Graph

Graph problems frequently appear in coding tests. A bipartite graph refers to a graph that can be divided into two sets, where adjacent vertices belong to different sets. In this lecture, we will learn about the algorithm to determine whether a graph is bipartite.

Problem Definition

Write a function to determine whether the given undirected graph is bipartite. A bipartite graph must divide the vertices into two groups, with no edges existing between vertices in the same group.

Input

• Number of vertices n (1 ≤ n ≤ 1000)
• Number of edges m (0 ≤ m ≤ 1000)
• Information on m edges (pairs of integers u, v indicating that vertex u is connected to vertex v)

Output

If the graph is a bipartite graph, print true, otherwise print false.

Approach to the Problem

To determine if a graph is bipartite, we can use a graph coloring technique. We color each vertex with two colors, such as ‘0’ and ‘1’, and if adjacent vertices are colored the same, the graph is not bipartite.

The implementation method is as follows:

• Represent the graph as an adjacency list
• Create an array to store the color of each vertex
• Use breadth-first search (BFS) or depth-first search (DFS) to visit and color the vertices
• If adjacent vertices have the same color, return that it is not a bipartite graph

Code Implementation

Let’s implement a function to determine whether a graph is bipartite according to the steps above using JavaScript.

function isBipartiteGraph(n, edges) {
    // Represent the graph as an adjacency list
    const graph = Array.from({length: n}, () => []);
    edges.forEach(([u, v]) => {
        graph[u].push(v);
        graph[v].push(u); // Since it is an undirected graph, add in both directions
    });

    const colors = Array(n).fill(-1); // Store the color of each vertex (-1: unvisited, 0: first color, 1: second color)

    const bfs = (start) => {
        const queue = [start];
        colors[start] = 0; // Color the starting vertex with the first color

        while (queue.length) {
            const node = queue.shift();

            for (const neighbor of graph[node]) {
                if (colors[neighbor] === -1) {
                    // If the adjacent vertex is unvisited, color it and add to the queue
                    colors[neighbor] = 1 - colors[node];
                    queue.push(neighbor);
                } else if (colors[neighbor] === colors[node]) {
                    // If the adjacent vertex's color is the same as the current node, it is not a bipartite graph
                    return false;
                }
            }
        }
        return true;
    };

    // Check all vertices and perform BFS if there are connected components
    for (let i = 0; i < n; i++) {
        if (colors[i] === -1) {
            if (!bfs(i)) return false;
        }
    }
    
    return true;
}

// Test case
const n = 4;
const edges = [[0, 1], [0, 2], [1, 3], [2, 3]];
console.log(isBipartiteGraph(n, edges)); // false
    

Algorithm Analysis

The above algorithm uses breadth-first search (BFS) to traverse all the vertices of the graph. Consequently, the time complexity is O(n + m) where n is the number of vertices and m is the number of edges. This is because we visit each vertex and edge once.

The space complexity is also O(n + m) required to store the adjacency list and color array.

Conclusion

In this lecture, we learned about the algorithm to determine whether a graph is bipartite. With this algorithm, we can ascertain if a graph problem involves a bipartite graph. Given its applicability to various problems, a thorough understanding is beneficial.

Furthermore, the solution to this problem can also be implemented similarly using DFS in addition to BFS. Understand the unique characteristics of the algorithm and try solving various derivative problems based on that.

Additional Practice Problems

To help your understanding, try solving the following problems:

• Symmetric Bipartite Graph Determination: Determine whether the given edge information constitutes a bipartite graph when provided symmetrically.
• Maximum Matching in Bipartite Graph: Implement an algorithm to find the maximum matching in a given bipartite graph.

References

For a detailed explanation of bipartite graphs, please refer to the Bipartite Graph article on Wikipedia.