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:

Go to the source code of this file.

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

Namespaces
namespace	graph
	Graph Algorithms.
namespace	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

Definition in file is_graph_bipartite.cpp.

Function Documentation

main()

int main

(

void

)

Main function

Testing

Definition at line 168 of file is_graph_bipartite.cpp.

           {
    test();  
    return 0;
}

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

Definition at line 136 of file is_graph_bipartite.cpp.

                   {
    graph::is_graph_bipartite::Graph G1(
        5);  
    G1.addEdge(1, 2);
    G1.addEdge(1, 3);
    G1.addEdge(3, 4);
    G1.addEdge(4, 5);
 
    graph::is_graph_bipartite::Graph G2(
        3);  
    G2.addEdge(1, 2);
    G2.addEdge(1, 3);
    G2.addEdge(2, 3);
 
    if (G1.is_bipartite()) {
        std::cout << "The given graph G1 is a bipartite graph\n";
    } else {
        std::cout << "The given graph G1 is not a bipartite graph\n";
    }
    if (G2.is_bipartite()) {
        std::cout << "The given graph G2 is a bipartite graph\n";
    } else {
        std::cout << "The given graph G2 is not a bipartite graph\n";
    }
}