• A graph is a data structure that has two types of elements, vertices and edges.
• The nodes are sometimes also referred to as vertices and the edges are lines or arcs that connect any two nodes in the graph.
• Graphs are used to solve many real-life problems.
• Graphs are used to represent networks. The networks may include paths in a city or telephone network or circuit network.

• Undirected, weighted simple grap

1. AddVertex()

• Adds a new node to the graph

• Takes in the value of that node

• Returns the added node

• Time complexity O(1), Space Complexity: O(1)

2. AddEdge()

• Adds a new edge between two nodes in the graph

• Include the ability to have a “weight”

• Takes in the two nodes to be connected by the edge

• Both nodes should already be in the Graph

• Time complexity is O(1) on average, O(n) worst case.

3. GetNodes()

• Returns all of the nodes in the graph as a collection (set, list, or similar)

• Time complexity is O(1), Space Complexity: O(1)

4. GetNeighbors()

• Returns a collection of nodes connected to the given node

• Takes in a given node

• Time Complexity: O(1), Space Complexity: O(1)

5. Size()

• Returns the total number of nodes in the graph

6. GetEdge()

• Write a function based on the specifications above, which takes in a graph, and an array of city names. Without utilizing any of the built-in methods, return whether the full trip is possible with direct flights, and how much it would cost.

Constructor Methods

Creates the Adjaceny List

• Input Vertices vertex
• Creates a new Linked List that holds Edges
• Increases Size of graph by 1

• Input - Vertex V1, Vertex V2
• Creates a new Linked List
• Add the Edge to the head of linked list.

• List of Vertices in the Graph

• Return Neighbors linked list

• Return Size of the Graph

• BreadthFirstTraversal
• Input = Vertex root
• Checks Vertices to see if start exists in graph.
• If start isnt in graph then null is returned.
• Create a queue
• Create a List
• If root is not visited then add it to the list
• return list

• Reference:

• https://www2.cs.duke.edu/courses/cps100e/fall10/class/11_Bacon/code/Graph.html