[SOLVED] algorithm graph CSE 331 Project 4 Unweighted Graphs

CSE 331 Project 4 Unweighted Graphs
TA: Yongqi Han
[email protected]
Office Hours: Tues/Thurs 4:30pm-6:30pm 3211 Anthony Hall, Study Loft
Due November 14th, 2019 at 11:59 pm
1 Project Description
You will implement breadth and depth first searching algorithms to determine whether a graph is bipartite. A bipartite graph, G= (V, E), is a graph such that a set of vertices, V, can be partitioned into two subsets, V1 and V2, and no edge has both its vertices in the same subset.
The two sets V1 and V2 may be thought of as a coloring of the graph with two colors: if one colors all nodes in V1 white, and all nodes in V2 black, each edge has endpoints of differing colors, as is required in the graph coloring problem. In contrast, such a coloring is impossible in the case of a non-bipartite graph, such as a triangle (three vertices and three edges): after one node is colored white and another black, the third vertex of the triangle is connected to vertices of both colors, preventing it from being assigned either color.
Your algorithm must run in a linear time. It must accept a single command line argument giving the name of a text file with an adjacency list for a graph. The first line of the input file will be either BFS, or DFS, indicating whether you should run a breadth or depth first search, respectively. The second line of the input file will be a single integer that specifies which node of the graph to start your

traversal. Each subsequent line in the text file contains a number indicating which vertex it is, followed by numbers separated by spaces, indicating which vertices this vertex has an edge to.
2 Programming Notes
You can assume that a given graph is connected.
You can assume that the node to start your traversal is valid.
When starting your traversal, you should start by coloring the initial node white.
After visiting a node, you should color all of its neighbors and then check for conflicts before visiting the next node.
Your solution must output the path it takes while traversing the graph. You will list the vertices and their colors in the order they are visited. Separate vertex and color by a single space (sample output shown below).
When deciding which neighbor of a vertex to visit next, always choose the smallest vertex (by number) that has not yet been visited. For example, if the neighbors of your current node are 5, 2, 7 then you should visit node 2 next.
If the graph is bipartite you must output true as the last line.
If the graph is not bipartite you can stop traversing the graph when you find the conflicting vertices. You must then output conflict followed by the conflicting vertices, and finally print false (see example output below).
You will be given a starter main.cpp which you are not allowed to modify. You will be given started Graph.h and Graph.cpp files that have function stubs for a few required functions. The rest of the implementation is up to you.
isBipartiteBFS() is where your BFS logic should be organized and printed. You can add any other helper functions that you need.
isBipartiteDFS() is where your DFS logic should be organized and printed. You can add any other helper functions that you need.

getTraverseMethod() needs to return either BFS or DFS depending on if you are running breadth or depth first search.
3 Sample Inputs/Outputs
g2 Sample Input for DFS
DFS
2
014 1023 2146 316 4025 546 6235
g1 Sample Input for BFS
BFS
2
012 1023 2013 312
Expected output for each of these inputs are shown below:
g1 Expected Output

g2 Expected Output
4 Project Deliverables
The following files must submitted (and automatically graded) via Mimir Classroom no later than 11:59 pm November 14th, 2019.
1. Graph.h and Graph.cpp containing your implementations of breadth and depth first search