Graph Algorithms

For this assignment, you will be coding 5 different graph algorithms. WARNING: This homework has quite a few files in it, so you should make sure to read ALL of the documentation given to you, including this pdf as well as all of the javadocs before asking a question.

Graph Representations

For this assignment, you will be using two different representations of graphs, the adjacency list and adjacency matrix. The adjacency list will be used for BFS, Dijkstra's, Prim's and Kruskal's. The adjacency matrix will be used for DFS. Generally, an adjacency matrix is better for when the graph is dense (many edges), and an adjacency list is better for when the graph is sparse (fewer edges). Also, it's worth noting from here on out, the time complexities will have two inputs, jV j to mean the number of vertices, and jEj to mean the number of edges. Although it is true that a simple graph can have at most jEj ≤ jV j(jV 2 j-1) = O(jV j2) edges, other than this, there isn't really any relationship between jV j and jEj. Keep in mind that the way that the graph is stored/represented will affect the time complexity of the algorithm. For example, for Dijkstra's algorithm, if an adjacency matrix is used, the time complexity is O(jV j2) while if an adjacency list with a priority queue is used, it is instead O(jEj + jV j log jV j).

Search Algorithms

The first two algorithms are breadth-first search (BFS) and depth-first search (DFS). These algorithms are search algorithms that start at the given vertex and traverse the entire graph in a particular order (the order in which the vertices are visited depend on whether you are doing breadth-first search or depth-first search, the edges that are in the graph, and the order the adjacent vertices are listed)