Is Graph Bipartite?

Introduction

In this blog post, we will explore the problem of determining if a given graph is bipartite. A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two adjacent vertices belong to the same set.

Problem Statement

Given an undirected graph represented as an adjacency list graph, we need to determine if it is bipartite.

Data Structure used

To solve this problem, we will use a stack and a vector to keep track of colors assigned to each vertex.

Algorithmic approach

We will use a depth-first search (DFS) approach to traverse the graph and assign colors to the vertices. The algorithm is as follows:

Initialize a vector colors with size equal to the number of vertices in the graph and set all values to -1, indicating that no color has been assigned.
Iterate through each vertex in the graph. If the color of the vertex is -1, perform the DFS algorithm.
Inside the DFS algorithm, push the current vertex onto a stack and assign it a color of 0.
While the stack is not empty, pop the top vertex from the stack and iterate through its neighbors.
- If the neighbor has not been assigned a color, assign it the opposite color of the current vertex (1 - colors[current]).
- If the neighbor has already been assigned a color and it is the same as the current vertex's color, return false, indicating that the graph is not bipartite.
If the DFS algorithm completes without finding any conflicts, return true, indicating that the graph is bipartite.

Implementation

bool isBipartite(vector<vector<int>> &graph)
{
    int n = graph.size();
    vector<int> colors(n, -1);

    for (int i = 0; i < n; ++i)
    {
        if (colors[i] == -1)
        {
            if (!isBipartiteDFS(graph, i, colors))
            {
                return false;
            }
        }
    }

    return true;
}
bool isBipartiteDFS(vector<vector<int>> &graph, int vertex, vector<int> &colors)
{
    stack<int> stk;
    stk.push(vertex);
    colors[vertex] = 0;

    while (!stk.empty())
    {
        int current = stk.top();
        stk.pop();

        for (int neighbor : graph[current])
        {
            if (colors[neighbor] == -1)
            {
                colors[neighbor] = 1 - colors[current];
                stk.push(neighbor);
            }
            else if (colors[neighbor] == colors[current])
            {
                return false;
            }
        }
    }

    return true;
}

Time Complexity

The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. The algorithm performs a DFS traversal, visiting each vertex and its adjacent edges once.

Space Complexity

The space complexity of this algorithm is O(V), where V is the number of vertices. The space is used to store the color assigned to each vertex in the graph.

Conclusion

In this blog post, we discussed the problem of determining if a graph is bipartite. We explored an algorithmic approach using depth-first search (DFS) and a stack to assign colors to the vertices. By understanding the problem requirements and implementing an efficient algorithm, we can determine if a given graph is bipartite.

Links:

Stackable