Project 2 undirected graph G=(V,E)

CS413: Project 2

As it appears in the course syllabus, you are expected to turn in the results of your own effort (not
the results of a friend's efforts)". Even when not explicitly asked, you should justify your answers
concisely.
Problem P: Given an undirected graph G=(V,E) where V is the set of nodes and E is the
set of edges and where |V|=n and |E|=m, we want to determine if the graph G, entered by
the user, has at least one cycle or not. As studied in the class, a cycle in a graph G is defined
as a closed chain of nodes where the first node and the last node in the chain are the same,
in another word the only repeated nodes are the first and the last nodes in the closed chain
or cycle. You may assume that graph G is connected, has no parallel edges and self-loops.
Task: Write a C++/Java program to solve problem P defined above. Your program should
return true if the graph has at least a cycle, and false otherwise. The runtime of your
program should not be exponential but it’s fine if it is not the best possible algorithm you
may write to solve the problem (Try to write the algorithm as efficient as you can in respect
to the time complexity and even space though).
Examples of user input:
Example 1:
The output of the algorithm should be true, as 3-2-4-3 is a cycle.
Example 2:
The output of the algorithm should be false.
You need to submit the program files to us, but in addition to that, you need to copy and
paste your FINAL CODE THAT YOU SUBMIT into a doc file that we call it the report
and submit it separately (do not compress the report together with your codes). Regarding
the report, if you have more than one file in your program, write the name of each program
file before its code comes in the report.
Deliverables:
1- The report you have provided as mentioned above. è Project 2 Report
2- The source code of your program that includes all .cpp or .java files. Put all files into a
folder and compress it. Then submit the zipped file. è Project 2 Code
Submission rules:
If the code you submit is different from the one you present in the report, you will get a
zero. That is, we DO NOT ACCEPT submissions that are different in the code and the
report.
You will get a zero if anyone of the deliverables are missing, or if the grader is not able to
run your code. No second chance will be given for file submission.
I will create two digital repositories for the project submission: one for the report (named
as Project 2 Report) and the other for the program files zipped into one file (named as
Project 2 Code).
Good luck!