Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
is_graph_bipartite.cpp File Reference

Algorithm to check whether a graph is bipartite More...

#include <iostream>
#include <queue>
#include <vector>
Include dependency graph for is_graph_bipartite.cpp:

Classes

class  graph::is_graph_bipartite::Graph
 Class for representing graph as an adjacency list. More...
 

Namespaces

 graph
 Graph algorithms.
 
 is_graph_bipartite
 Functions for checking whether a graph is bipartite or not.
 

Functions

static void test ()
 
int main ()
 

Detailed Description

Algorithm to check whether a graph is bipartite

A graph is a collection of nodes also called vertices and these vertices are connected by edges. A graph is bipartite if its vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.

The algorithm implemented in this file determines whether the given graph is bipartite or not.

 Example - Here is a graph g1 with 5 vertices and is bipartite
    1   4
   / \ / \
  2   3   5
Example - Here is a graph G2 with 3 vertices and is not bipartite
  1 --- 2
   \   /
     3
Author
Akshat Vaya

Function Documentation

◆ main()

int main ( void  )

Main function

Testing

168  {
169  test(); /// Testing
170  return 0;
171 }
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function to test the above algorithm

Returns
none

creating graph G1 with 5 vertices

adding edges to the graphs as per the illustrated example

creating graph G2 with 3 vertices

adding edges to the graphs as per the illustrated example

checking whether the graphs are bipartite or not

136  {
138  5); /// creating graph G1 with 5 vertices
139  /// adding edges to the graphs as per the illustrated example
140  G1.addEdge(1, 2);
141  G1.addEdge(1, 3);
142  G1.addEdge(3, 4);
143  G1.addEdge(4, 5);
144 
146  3); /// creating graph G2 with 3 vertices
147  /// adding edges to the graphs as per the illustrated example
148  G2.addEdge(1, 2);
149  G2.addEdge(1, 3);
150  G2.addEdge(2, 3);
151 
152  /// checking whether the graphs are bipartite or not
153  if (G1.is_bipartite()) {
154  std::cout << "The given graph G1 is a bipartite graph\n";
155  } else {
156  std::cout << "The given graph G1 is not a bipartite graph\n";
157  }
158  if (G2.is_bipartite()) {
159  std::cout << "The given graph G2 is a bipartite graph\n";
160  } else {
161  std::cout << "The given graph G2 is not a bipartite graph\n";
162  }
163 }
Here is the call graph for this function:
test
static void test()
Definition: is_graph_bipartite.cpp:136
std::cout
graph::is_graph_bipartite::Graph
Class for representing graph as an adjacency list.
Definition: is_graph_bipartite.cpp:51