## Description

## Overview

This project is to create a graph. A graph is a collection of vertices and edges that connect pairs of

vertices. Graphs can be used to represent many real-world problems. The goal of this project is to

build a graph and allow a user to explore and search that graph. Like other projects, this will build

upon previous programming techniques used.

## Requirements

You will read in a set of edges from a text file and construct a graph, represented internally using the

adjacency list data structure. Once the graph is constructed, let the user pick a starting vertex and

display the list of vertices they may travel to. They enter the number of the vertex, move to that

vertex, and the process repeats. If they enter a vertex that isn’t adjacent to the current vertex, you

should display a message saying the move isn’t valid and keep them at the current vertex.

In addition to this, you must also have display functionality that displays the entire graph. Nothing

fancy required, just display a list of vertices, a colon, and then all the vertices adjacent to that vertex.

Finally, implement a search method. This will let the user enter a value, your search algorithm will

search the graph for it, starting at the current vertex, and then report if the value was found or not

on the graph. You may implement this using Breadth First Search (BFS) or Depth First Search (DFS).

Sample Output

This is just an example. Feel free to display the output and menus however you would like.

Loading graph from “smallGraph.txt”.

Please enter the vertex to start at: 1

Currently at vertex: 1. Adjacent vertices: 5, 6, 10

What would you like to do? (M)ove (P)rint Graph (S)earch?: M

Please enter the vertex: 10

Currently at vertex: 10. Adjacent vertices: 1, 6, 2

What would you like to do? (M)ove (P)rint Graph (S)earch?: S

Please enter the value to search for: 8

Vertex 8 was found in this graph.

Currently at vertex: 10. Adjacent vertices: 1, 6, 2

What would you like to do? (M)ove (P)rint Graph (S)earch?: P

1: 5, 6, 10

2: 10, 4

3: 7

4: 2, 8, 7

(and so forth…)

### Programming Languages

You may use any programming language as long as you confirm it with me first. This course will be

centered Java, so that is my recommendation.

Dataset

Three different graph datasets are provided. The first value in these text files will be the number of

vertices. You can use the number of vertices to dynamically declare the size of your adjacency list.

After that, each line contains an edge, which is really just two vertices separated by a space.

Hints

The adjacency list data structure is really an array of linked lists. You may be able to reuse Linked

List code if you have it. Make sure to reject invalid moves if attempted. It may be helpful to manually

draw out the graph.

Extra Credit

If you’re looking for an extra challenge, here are some extra features you may add for extra points.

Once you have basic graph functionality there are a ton of features you could add.

• When doing your search, display the resulting path used to find the result and the length of

the path (if result is found).

• Add needed functionality to turn the graph into a directional graph. Assume the edges in the

text files you’re reading in are only one way (this may be easier than you’d think).

• Implement both depth first and breadth first searching.

• Add a check to determine if the graph is fully connected and display if it is or not.

Grading

The assignment is worth 100 points. If your code doesn’t compile, there is an immediate 30-point

penalty. You will be graded on the following criteria:

Header comment block with name, class, date, project 10

Graph is read from input and constructed using adjacency lists 20

Graph traversal 20

Graph print feature 10

Graph searching algorithm 30

Overall organization and quality of code 10

Total 100

Submitting your work

Your work should be submitted as an archive (.zip, .7z, .rar) on Moodle. This archive should include

all of your source code files. Please do not submit your entire project folder.

This project is due Friday, April 12that 11:59pm.