Chapter 6: Graph Algorithms I

Activity 13: Finding out Whether a Graph is Bipartite Using DFS

In this activity, we will check whether a graph is bipartite using depth-first search traversal. Follow these steps to complete the activity:

1. Add the required header files and declare the graph to be used:

   #include <string>
   #include <vector>
   #include <iostream>
   #include <set>
   #include <map>
   #include <stack>
   template<typename T> class Graph;

2. Write the following struct to define an edge in our graph:

   template<typename T>
   struct Edge
   {
       size_t src;
       size_t dest;
       T weight;
       // To compare edges, only compare their weights,
       // and not the source/destination vertices
       inline bool operator< (const Edge<T>& e) const
       {
           ...