Bipartite Graph Check in DSA Typescript - Build from Scratch

Bipartite Graph Check

📖 Scenario: You are working on a social networking app. You want to check if the users can be split into two groups so that no two friends are in the same group. This helps in organizing events where friends from different groups meet.

🎯 Goal: Build a program that checks if a given graph of users and their friendships is bipartite. A bipartite graph means you can divide users into two groups with no friendships inside the same group.

📋 What You'll Learn

Create a graph using an adjacency list with exact user connections

Add a color array to track group assignments

Implement a function to check if the graph is bipartite using BFS

Print the result as true or false

💡 Why This Matters

🌍 Real World

Checking bipartite graphs helps in scheduling, grouping people, and solving problems where two distinct sets must be formed without internal conflicts.

💼 Career

Understanding bipartite graphs is useful for software engineers working on social networks, recommendation systems, and network analysis.

1

Create the graph adjacency list

Create a variable called graph as an array of arrays representing the adjacency list for 4 users with these exact connections: user 0 connected to 1 and 3, user 1 connected to 0 and 2, user 2 connected to 1 and 3, user 3 connected to 0 and 2.

DSA Typescript

# Your code here

Hint

Use a constant named graph and assign it an array of arrays with the exact connections.

2

Add a color array to track groups

Create a variable called color as an array of length 4 filled with -1 to represent uncolored users.

DSA Typescript

const graph: number[][] = [[1, 3], [0, 2], [1, 3], [0, 2]];
# Your code here

Hint

Use new Array(4).fill(-1) to create the color array.

3

Implement the bipartite check function

Write a function called isBipartite that takes graph and color as parameters. Use a for loop with variable start from 0 to graph.length. Inside, if color[start] is -1, assign color[start] = 0 and use a queue to perform BFS. For each node, check neighbors: if uncolored, assign opposite color; if same color, return false. Return true if no conflicts.

DSA Typescript

const graph: number[][] = [[1, 3], [0, 2], [1, 3], [0, 2]];
const color: number[] = new Array(4).fill(-1);
# Your code here

Hint

Use BFS with a queue and assign colors 0 and 1 to neighbors. Return false if a conflict is found.

4

Print the bipartite check result

Write a console.log statement to print the result of calling isBipartite(graph, color).

DSA Typescript

const graph: number[][] = [[1, 3], [0, 2], [1, 3], [0, 2]];
const color: number[] = new Array(4).fill(-1);

function isBipartite(graph: number[][], color: number[]): boolean {
    for (let start = 0; start  0) {
                const node = queue.shift()!;
                for (const neighbor of graph[node]) {
                    if (color[neighbor] === -1) {
                        color[neighbor] = 1 - color[node];
                        queue.push(neighbor);
                    } else if (color[neighbor] === color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
# Your code here

Hint

Call console.log(isBipartite(graph, color)) to print the result.