Graph Traversal Algorithms

Overview

In class we talked about the Graph data structure and several graph algorithms. For this project you are going to implement several of them.

Student Learning Outcomes

• Implement a queue data structure using a circularly simple linked list.
• Implement a graph using an adjacency list.
• understand Node pointers
• understand objects within objects
• comprehend starter code
• implement DFS and BFS algorithms

Implementation Details

For this project you are going to implement an adjacency list graph (AdjListGraph), a queue (MyQueue), depth first traversal, and breath first traversal.

MyQueue

This is a queue that you will use for the breath first traversal.

• You will implement it on a circular simple linked list that you will create.
• The nodes will hold an integer value and a Node pointer next.
• You will have a tail pointer but no head pointer
• You will implement the add(int):void, remove:int, size:int, and isEmpty:boolean methods.

AdjListGraph

This is a simplified directed graph data structure. This data structure will use the adjacency list representation for a graph. The adjacency list will be an array that holds Nodes that represent the vertex. Then the next field of the node will point to the first neighbor. i.e. adjList[0] will give the Vertex (Node) labeled 0 and adjList[0].next is equivalent to the head pointer to the linked list of 0's neighbors.

• Your constructor should:
  • create an adjList array of the parameter passed size.
  • each spot in the adjList should be filled with a vertex. The values (aka labels) should be node 0 to size -1.
  • FYI: You can assume that adjList[X] is never null because of this step.
  • Add edges to the list of edges by utilizing the addEdge method. See in-code comment for details.
• addEdge(int vertexFrom, int vertexTo):void
  • as a directed edge to the graph.
• An unmark method has been provided.
• breathFirstTraversal:String
  • complete a breath first traversal starting at vertex 0.
  • As you process nodes, add them to a string that will be returned.
  • Bracket the string with square brackets.
  • You should use your MyQueue class
• depthFirstTraversal
  • complete a depth first traversal starting at vertex 0.
  • As you process nodes, add them to a string that will be returned.
  • Bracket the string with square brackets.
  • You should use the java library Stack. (java.util.Stack)