# Program 1 Solution

\$30.00

Category:

## Description

Functional Requirements

Write a Java program (based on a graph traversal algorithm you’ve learned in this class) that, for a given undirected graph, outputs: (i) vertices of each connected component; (ii) a cycle or a message that the graph is acyclic (if there are more than one cycles in a graph, you are required to output just one of them).

Your programs should take inputs from a file via the command line with the following structure in the input file. Each line of the input file represents a graph. The first number in a line species the number of vertices in the graph. Then pairs of vertices define the edges.

An example of an input file is as follows:

5 (1,2) (3,4) (3,5) (4,5)

4 (1,2) (2,3) (1,4)

It specifies two graphs. The first graph has five vertices (1,2,3,4,5) and four edges. The second graph has four vertices (1,2,3,4) and three edges.

Proper output should look (something) like:

• −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

Graph1:

Two connected components: {1 2} {3 4 5}

Cycle detected: 3 – 4 – 5 – 3

Graph2:

One connected component: {1 2 3 4}

The graph is acyclic.

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

You must test your programs on a nontrivial input file (with at least 3 graphs and each graph having 7-10 nodes). For the second problem, your test graphs should cover both cyclic and acyclic graphs. Your output should be formatted nicely so that it is easy to read.

Your program should use “good style”. See the separate handout on style requirements for CS-203 programs. In particular, note that you should describe the algorithms you implement

1

in suﬃcient detail to demonstrate your deep understanding of the algorithms in question.

Additionally, you should create the following ordinary text file:

Before 11:59:59 p.m., Tuesday, 23 October 2018 (4th Tuesday), you must upload a zip archive to the course Blackboard assignment for Programming Assignment 1. This zip archive must contain all source code files for your program, including a class named PROG1 with a MAIN method.

No code printouts are required.