Bipartite graphs

From Algorithmist
Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

A graph is bipartite if and only if it is bicolorable. So, to decide if it is bipartite, we can try to bicorate it with a DFS:

bool dfs(int node, int color)
{
  if(color[node] != 0)
    {
      if(color[node] == color)
        {
          return true;
        }
      else
        {
          return false;
        }
    }
  color[node] = color;
  for(int i = 0; i < degree[nod]; ++i)
    {
      if(!dfs(adj[node][i], -color))
        {
          return false;
        }      
    } 
  return true;
}