In this assignment, we will receive the adjacency matrix of a weighted undirected graph from a text file and do the following:

1. output its connected components, one per line when each connected component is represented as the set of its vertices; 30%
2. output one cycle as u_1 u_2 ...u_i .... u_1 if the graph has any cycles, or output "No cycles" if it doesn't; 40%
3. output all the edges in the minimum spanning trees of each of its components. 30%

You must call your file GraphProcessor.cpp and it MUST run as follows:

g++ -o GraphProcessor.o GraphProcessor.cpp
./GraphProcessor.o graph1.txt
Connected components:
{0,1,2,4,7}
{3}
{5,6}
A cycle: 0 1 4 2
Edges in minimum spanning trees:
0 1
1 7
2 7
2 4
5 6
./GraphProcessor.o graph2.txt
Connected components:
{0,1,2,3,4}
No cycles
Edges in minimum spanning trees:
0 1
1 4
0 2
1 3

Some points to keep in mind

1. Make sure you click on the graph1.txt and graph2.txt links above to see the input format and to understand why the program is outputting what it's outputting.
2. If there are more than one cycles, outputting any cycle will do.
3. It is possible for a connected component to have multiple minimum spanning trees. If that's the case, choosing any one of them for each connected component is OK.
4. The order of lines in connected components or in set of edges in minimums spanning trees doesn't matter.
5. The order of vertices in the cycle does matter: it should give us the cycle!
6. The vertices inside a connected component should be in increasing order.
7. The order of vertices in an edge should be in increasing order.

What to submit?

1. GraphProcessor.cpp

Where to submit?

In CourSys under CMPT 225 Assignment6 activity.

Final Note

While it is OK for you to discuss the high-level idea of how to tackle each of these steps among yourselves, I encourage you to try coming up with the idea yourself. Remember, one of the most important goals of the course is to build your problem-solving skills.

Also, remember that out of all six assignments, one worst grade will be discarded. So, if you have got 100% of all other assignments so far, you won't get more marks by handing in this one. However, it is a good exercise to do the assignment, and even if you decide not to do it, I highly encourage you to try coming up with the ideas. It may prove useful in the final exam.

---