Write a function named bipartiteSets that accepts a reference to a BasicGraph as a parameter and attempts to divide the graph's vertices into two bipartite sets.
A bipartite graph is one whose vertices can be divided into two independent sets in such a way that for any edge E connecting vertices V1 and V2, vertex V1 is in the first set and vertex V2 is in the second set, with no edge in the graph ever connecting two vertices that are in the same set.
For example, Graph 1 below is bipartite because its vertices can be divided into the sets {A, C, F} and {B, D, E, G} because every edge connects a vertex from {A, C, or F} with one from {B, D, E, or G}.
So if your function were called on that graph, it should print console output displaying the sets of vertex names in the following format:
set 1: {"A", "C", "F"}
set 2: {"B", "D", "E", "G"}
and should return the Boolean result of true to indicate that suitable bipartite sets can be found.
(Some graphs have multiple bipartite set orderings; in such a case, your function can print any valid pair of bipartite sets, and the elements can appear in the sets in any order in the output, so long as the sets are valid.)
Graph 2 below is not bipartite; its vertices cannot be divided into two appropriate sets.
So your function would print no output and would return false.
An empty or one-vertex graph should be considered bipartite.
There are several ways to solve this problem.
One common way is to visit vertices and giving them markings or colors much as you might do in a breadth-first or depth-first search.
By alternating colors between neighbors as you go along, and making sure that no vertex is ever given two different colors while you are exploring, you can see whether the graph is able to be divided into two bipartite sets.
(Our description of this algorithm is intentionally somewhat vague because we want you to think about the details of how to implement it yourself.)
Assumptions:
You may assume that the graph's state is valid and that no two vertices have the same name.
You may also assume that the graph is connected (that there exists a path from every vertex to every other vertex) and that it is undirected, in the sense that if there is an edge from vertex V1 to V2, there is also an edge from V2 to V1.
You may assume that the graph contains no self-edges (e.g. from V1 to V1).
Constraints:
You may define private helper functions if so desired, and you may construct auxiliary collections as needed to solve this problem.
You should not modify the contents of the graph such as by adding or removing vertices or edges from the graph, though you may modify the state variables inside individual vertices/edges such as visited, cost, and color.
Your code must run in no worse than O(V log V + E log E) time, where V and E are the number of vertices and edges in the graph respectively.
(It is possible to solve it in O(V + E) time.)
